Talk:Maximum subarray problem

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)[reply]

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)[reply]

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)[reply]

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:

Kadane_s_Algorithm(arr[1..n])
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)[reply]

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)[reply]

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)[reply]

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)[reply]

Because the empty sum has a larger total than sums of one or more elements. —David Eppstein (talk) 23:44, 31 July 2010 (UTC)[reply]

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)[reply]