Talk:Maximum subarray problem: Difference between revisions

Revision as of 02:09, 12 May 2020

Revision as of 20:33, 7 May 2022

Line 5:

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

<sourcesyntaxhighlight lang="cpp">

int s=1<<31;

</syntaxhighlight>

</source>

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

Line 16:

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

: <sourcesyntaxhighlight lang="cpp">

int s = numeric_limits<int>::min()

</syntaxhighlight>

</source>

: or to MIN_INT in C

Line 32:

The correct algorithm is:

<sourcesyntaxhighlight lang="pascal">

Kadane_s_Algorithm(arr[1..n])

begin

Line 52:

return (max, a, b)

end

</syntaxhighlight>

</source>