(top of my head) I would keep the minimum and the sum for each interval, and just calculate the max of the sum times the minimum for each interval (the trick is store the minimum of each interval to avoid O(n) searches each time you calculate the max)
sorry for the quick response... must go on working
On 6/26/06, Pradeep Muthukrishnan <[EMAIL PROTECTED]> wrote:
can u please explain the recurrence? I have been thinking abt DP but
could never find a recurrence
On 6/26/06, Guillermo Garcia <[EMAIL PROTECTED]> wrote:
> Try dynamic programming
>
>
>
> On 6/26/06, Pradeep Muthukrishnan < [EMAIL PROTECTED]> 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
> >
> >
> >
> >
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
