Talk:Maximum subarray problem: Difference between revisions

Revision as of 04:22, 10 April 2012

Revision as of 17:31, 16 November 2013

Line 56:

No, it finds any subarray of the whole array. That's what the line "max_ending_here = max(0, max_ending_here + x)" is for: the points where the max is 0 are the ones where a new subarray starts. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 06:28, 15 June 2010 (UTC)

I confirm that the shown solution is incorrect. Given the following array:

{5,-2,4,-6,1,3, -7 , 3, 10, -15, -4 ,3, -2, 16, -9, 10};

Applying the algorithm as shown in the page, I get a maximum subarray of 11, whereas the maximum subarray should be 13 (3 + 10)

== Clarification of maximum sum when maximum sum is < 0. ==