Content deleted Content added
→Incorrect solution: new section |
|||
Line 27:
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
[[Special:Contributions/217.132.204.221|217.132.204.221]] ([[User talk:217.132.204.221|talk]]) 05:47, 15 June 2010 (UTC)
| |||