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. * If the optimal internal containing a[m] contains one element, it is simply a[m] * If it contains more than one element, it must contain the larger of a[m-1] and a[m+1], so add this to the interval. (If it contains the smaller of the two, you can only improve the solution by also including the larger of the two.) * Let's assume the element in the previous step was a[m-1]. Now, if the optimal interval contains more than two elements, it must contain the larger of a[m-2] and a[m+1]. * Etc. * Return the best interval of any size constructed by this process. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
