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