Content deleted Content added
syntaxhighlight & fix lint |
|||
| (12 intermediate revisions by 8 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:
<
int s=1<<31;
</syntaxhighlight>
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++)
: <
int s = numeric_limits<int>::min()
</syntaxhighlight>
: or to MIN_INT in C
Line 32 ⟶ 34:
The correct algorithm is:
<
Kadane_s_Algorithm(arr[1..n])
begin
Line 52 ⟶ 54:
return (max, a, b)
end
</syntaxhighlight>
Line 65 ⟶ 67:
<s>Applying the algorithm as shown in the page, I get a maximum subarray of 11, whereas the maximum subarray should be 13 (3 + 10)</s> <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/187.194.146.244|187.194.146.244]] ([[User talk:187.194.146.244|talk]]) 17:31, 16 November 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
(Scratch previous comment, the algorithm is correct)
The solution given in python is incorrect. Please remove the code.
it fails following case: [-2,1,-3,4,-1,2,1,-5,4]. Should produce 6, instead of 10.
== Clarification of maximum sum when maximum sum is < 0. ==
Line 98 ⟶ 105:
== the solution for keeping track of the indices for the subarray is wrong ==
here is a working script
<syntaxhighlight lang="text">
max_ending_here = A[0]
Line 120 ⟶ 128:
print (max_so_far , start, end)
</syntaxhighlight>
== Issues with the "History" section, regarding brute-force ==
It seems incorrect that "the brute force running time" of the one-dimensional problem is "''O''(''n''<sup>3</sup>)". This is not right.
Rather, the brute-force runtime is ''O''(''n''<sup>2</sup>). What, then, I wonder, did Ulf Grenander's improvement do? This is confusing.
I suspect that there are similar issues with the description of the two-dimensional problem's history.
I'm not clear on the history, or else I would edit this myself...!
:The brute force algorithm tries <math>O(n^2)</math> different subarrays and takes time <math>O(n)</math> to compute the sum for each of them, giving <math>O(n^3)</math> total. Maybe you are already thinking of optimizing it to be faster? But then it's not the most obvious and basic version of the algorithm any more. And optimizing a bad algorithm is wasted effort. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 04:06, 7 August 2019 (UTC)
== History is weird ==
<blockquote>
Soon after, Shamos described the one-dimensional problem and its history at a Carnegie Mellon University seminar attended by Jay Kadane, who designed within a minute an O(n)-time algorithm, which is clearly as fast as possible.
</blockquote>
The previous comment wonders out loud about the history section, and I have to wonder, too.
<blockquote>
Knuth began the project, originally conceived as a single book with twelve chapters, in 1962.
:
The first three volumes of what was then expected to be a seven-volume set were published in '''1968''', '''1969''', and '''1973'''.
:
Work began in earnest on Volume 4 in 1973, but was suspended in 1977 for work on typesetting.
</blockquote>
Supposedly, this anecdote takes place in 1977. By 1977, if you couldn't derive the O(1) algorithm for the one-dimensional case within 30 minutes, you were seriously in the wrong professional already. The only viable excuse would be a three martini lunch.
What ''really'' was going on here? Because I doubt any of these men were quite that dense upstairs.
For example, I suspect the guy agonizing over the divide and conquer thought he was solving a somewhat generalized version of the problem statement here, for which some of that heavy machinery would have actually been appropriate.
As written, this does not pass my historical smell test. — [[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)
| |||