# Talk:Maximum subarray problem

WikiProject Computer science
This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.

## Possibly Erroneous Initialization of s

In the O(n) algorithm, s (the largest calculated sum so far) is initialized as follows:

int s=1<<31;

First, this assumes that each integer is exactly 4 bytes wide, which is not the case for all architectures.

Second, it seems sufficient to initialize it to the first element of the array, A[0]

Debajit (talk) 23:29, 25 November 2007 (UTC)

I've struck out my second proposition, which would fail for sequences having exactly one element. For my first proposition, I think s is best initialized to -Infinity as (for C++)
int s = numeric_limits<int>::min()
or to MIN_INT in C
Debajit (talk) 23:45, 25 November 2007 (UTC)

## Notability

I have seen a few publications in IEEE and JSTOR refering to this algorithm. I have no understanding of the algorithm itself, therefore I cannot verify the accuracy of the information here, but I would conclude that this article is based on a notable topic. --MattWatt 22:07, 10 April 2007 (UTC)

## Incorrect solution

Kadane's algorithm is not a solution for general maximum subarray problem: it only finds maximum subarray starting from the brginning of array, not any subarray.

The correct algorithm is:

begin
(max, a, b) := (-INFINITY, 0, 0)
curr := 0
aa := 1
for bb := 1 to n do
curr := curr + arr[bb]
if curr > max then
(max, a, b) := (curr, aa, bb)
endif

if curr < 0 then
curr := 0
aa := bb + 1
endif
endfor

return (max, a, b)
end

217.132.204.221 (talk) 05:47, 15 June 2010 (UTC)

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. —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) — Preceding unsigned comment added by 187.194.146.244 (talk) 17:31, 16 November 2013 (UTC) (Scratch previous comment, the algorithm is correct)

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

If I pass in an array of entirely negative numbers, e.g. (-1,-1,-1,-1), why wouldn't the maximum sum be -1 instead of 0? —Preceding unsigned comment added by 76.247.17.199 (talk) 22:47, 31 July 2010 (UTC)

Because the empty sum has a larger total than sums of one or more elements. —David Eppstein (talk) 23:44, 31 July 2010 (UTC)
That's not necessarily true. If you want to include negative sums, first increase max_ending_here, then if max_ending_here > max_so_far, replace max_so_far, THEN if max_ending_here < 0, set it to 0. In that way the max will contain the closest negative member to 0 for an all negative array. (Alternatively, you could just find the max member if the resulting max == 0 and it will still be O(n)) -April 9, 2012 — Preceding unsigned comment added by 128.138.45.66 (talk) 04:21, 10 April 2012 (UTC)