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) > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
