[algogeeks] Re: Nice question!!

Tue, 27 Jun 2006 09:32:52 -0700

Sorry,
         I did not read the Gene's solution properly. Great work Gene. I doubt the solution given above.

 
On 6/27/06, Googmeister <[EMAIL PROTECTED]> 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
 
 
How will this solution work in which the optimal subset  in a[m-x]......a[m+y]. That is the solution extends over the two splitted half of the arrays. I am not getting any points commented as *. Can you please explain?

* 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.



http"//ww.livejournal.com/users/arunachalam
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---

Reply via email to