Gene wrote: > Googmeister wrote: > > Pradeep Muthukrishnan wrote: > > > I have been trying this problem for quite some time now...but havent > > > found anything concrete...can anyone solve this? > > > http://acm.zju.edu.cn/show_problem.php?pid=2642 > > > > Here's a O(n log n) mergesort style solution: > > > > * Divide the elements in the middle: a[l..m-1], a[m], a[m+1..r] > > * Recursively compute the optimal interval entirely in the left half > > * Recursively compute the optimal interval entirely in the right half > > * Compute the optimal interval containing a[m] > > * Return the best of the three intervals > > > > The key step for efficiency is computing the optimal > > interval containing a[m] in linear time. Here's a greedy solution. > > Hi Gm, > > If finding this interval requires linear time, then the run time is > proprtional to n^2
No. It's the standard n log n recurrence. > because there is no bound on the size of the > interval you're searching for Yes there is. At each recursive call the size of the interval shrinks by a factor of 2. Once you've divide the interval, you no longer need to worry about intervals crossing the border. > and each of n elements must eventually > become a[m] That's true. But the size of the interval left to examine will be 1 or 2 for most of them. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
