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 because there is no bound on the size of the interval you're searching for and each of n elements must eventually become a[m] That's why I proposed choosing these "pivots" in sorted order. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
