Talk:Maximum subarray problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science  
WikiProject icon 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.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

Possibly Erroneous Initialization of s[edit]

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[edit]

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[edit]

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)

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.[edit]

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)

Kadane's algorithm code[edit]

I am finding it difficult to believe that we should just scrap the C++ code in this section. I think that before we do that we should implement the ability to track indices in the Python version as well. The C++ code did this, but the Python code does not. Mrcsmcln (talk) 11:45, 2 October 2014 (UTC)

Wikipedia is not a code repository. We should not have 20 different implementations of the same algorithm in 20 different programming languages, or even 2. Multiple implementations are ok only when they show significant variations in the algorithms, and tracking indices is not a significant variation. Pseudocode might be a better choice than any specific language, but Python is closer to pseudocode than C++ is. —David Eppstein (talk) 15:04, 2 October 2014 (UTC)

I added an external link to the corresponding Rosetta Code page (where it is called greatest subsequential sum algorithm), there are implementations in many other languages as well Andre.holzner (talk) 12:28, 27 August 2016 (UTC)