Talk:Maximum subarray problem: Difference between revisions

Revision as of 02:09, 12 May 2020

Latest revision as of 14:05, 14 January 2025

(5 intermediate revisions by 3 users not shown)

Line 1:

{{WikiProject banner shell|class=|

{{WikiProject Computer science}}

}}

== Possibly Erroneous Initialization of s ==

Line 5 ⟶ 7:

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 ⟶ 18:

: 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 ⟶ 34:

The correct algorithm is:

<sourcesyntaxhighlight lang="pascal">

Kadane_s_Algorithm(arr[1..n])

begin

Line 52 ⟶ 54:

return (max, a, b)

end

</syntaxhighlight>

</source>

Line 105 ⟶ 107:

here is a working script

<syntaxhighlight lang="text">

<code>

max_ending_here = A[0]

Line 126 ⟶ 128:

print (max_so_far , start, end)

</syntaxhighlight>

</code>

== Issues with the "History" section, regarding brute-force ==

Line 162 ⟶ 164:

As written, this does not pass my historical smell test. &mdash; [[user:MaxEnt|MaxEnt]] 02:09, 12 May 2020 (UTC)

== Empty subarrays admitted vs. forbidden ==

In order to reduce the number of good-faith edits like [https://en.wikipedia.org/w/index.php?title=Maximum_subarray_problem&diff=1174756409&oldid=1165256313 the most recent one], what about presenting the "''No empty subarrays admitted''" variant first, and in full detail, and then just the changes needed to turn it into the "''Empty subarrays admitted''" variant? If we are lucky, most over-hasty ad-hoc page editors are familar with the "''No empty subarrays admitted''" variant, and won't change the text, since it meets their expectations. However, if we are unlucky, the favorite variants are distributed 50:50, and we'd experience lots of thoughtless edits in the opposite direction. I think, implementing my suggestion is worth a try. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 14:55, 10 September 2023 (UTC)

:I'm skeptical that this will help but it seems harmless enough and worth a try. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:45, 10 September 2023 (UTC)

::{{done}}. Some complications were caused by the fact that both Bentley and Gries refer to the "empty" variant, while we start with the "nonempty" variant. The worst of them is the new [note6] which now has to explain a modification the Bentley should have made in the ''previous'' (rather than the ''current'') variant. - I gave the essential loop invariants for both algorithm variants; they could (after some days of trial and error) be verified by [[Frama-C]], so they shouldn't be flawed. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 15:28, 13 September 2023 (UTC)