Dyanesh, ... precisely! On 8/25/07, Dhyanesh (ધયાનેશ) <[EMAIL PROTECTED]> wrote: > > If you think of your DP solution, it is almost the same as the previous > O(n) solution you gave. That one is also DP in way that you store just one > previous solution. > -Dhyanesh > > On 8/24/07, Lego Haryanto <[EMAIL PROTECTED]> wrote: > > > I should take my statement regarding the O(n) space for DP back ... > > > > If we don't care storing each intermediate result, ... then space is > > also O(1). > > > > > > On 8/24/07, Lego Haryanto <[EMAIL PROTECTED]> wrote: > > > > > For the DP recurrence, consider f(i) is the "best contiguous sum > > > ending at this index i". > > > > > > f(i) = a[i], if i == 0 > > > f(i) = max(a[i], f(i-1)+a[i]), on other cases > > > > > > Basically, for each index i, to end a subarray ending at i, it's > > > obvious that we can either "extend" the best solution for previous index, > > > or > > > we can start our own. > > > > > > Now, the maximum subarray sum would be the max(f(i)), for i = 0 .. > > > n-1. > > > > > > > > > On 8/24/07, Lego Haryanto <[EMAIL PROTECTED] > wrote: > > > > > > > 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) > > > > > > > > > > > > > > > > -- > > > Fear of the LORD is the beginning of knowledge (Proverbs 1:7) > > > > > > > > > > > -- > > 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 -~----------~----~----~----~------~----~------~--~---
