I thought I already answered earlier even thought it's just words and no
code.
sum = 0
best = -INF
FOREACH val IN a DO
sum = sum + val
best = MAX(best, sum)
IF sum < 0 THEN sum = 0;
ENDFOR
O(n) runtime, O(1) space.
DP can be done as well in O(n), but due to the nature of DP, you'll need
O(n) space as well.
On 8/24/07, ilija <[EMAIL PROTECTED]> wrote:
>
>
> I would like to see your code for the first case.
> I really doubt that there exists an O(n) algo for this.
>
> On 23 kol, 16:11, "Lego Haryanto" <[EMAIL PROTECTED]> wrote:
> > Either case is O(n), in fact.
> >
> > On 8/23/07, ilija <[EMAIL PROTECTED]> wrote:
> >
> >
> >
> > > If the subarray needs to be continuous, then you can do it using DP.
> > > If it doesn't, you can do it using an O(n) algo - simply sum all the
> > > positive integers.
> >
> > > On 22 kol, 19:55, Ravi <[EMAIL PROTECTED]> wrote:
> > > > You're given an array containing both positive and negative integers
> > > > and required to find the subarray with the largest sum.
> > > > Write a routine in C for the above.
> >
> > --
> > Fear of the LORD is the beginning of knowledge (Proverbs 1:7)
>
>
> >
>
--
Fear of the LORD is the beginning of knowledge (Proverbs 1:7)
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
