Content deleted Content added
Undid revision 1147540473 by Onewikibarnes (talk) You still haven't even tried running the code as is, have you? It works correctly on your supposed incorrect examples. Stop messing with things you obviously aren't competent to understand. |
→Kadane's algorithm: partially reverting deletions of 5 Mar 2023 (keeping code omitted): apparently, the no-empty-subarrays-admitted version is in widespread use, so we'd better mention it in a subsection header to prevent further misunderstandings like the most recent one by Onewikibarnes |
||
Line 78:
This algorithm calculates the maximum subarray ending at each position from the maximum subarray ending at the previous position, so it can be viewed as a trivial case of [[dynamic programming]].
===No empty subarrays admitted===
For the variant of the problem which disallows empty subarrays, <code>best_sum</code> should be initialized to negative infinity instead{{sfn|Bentley|1989|p=78,171}} and also in the for loop <code>current_sum</code> should be updated as <code>max(x, current_sum + x)</code>.{{NoteTag
|While the latter modification is not mentioned by {{harvtxt|Bentley|1989}}, it achieves maintaining the modified loop invariant <code>current_sum</code><math>=\max_{i \in \{ 1, ..., j \}} A[i]+...+A[j]</math> at the beginning of the <math>j</math>th step.
}}
In that case, if the input contains no positive element, the returned value is that of the largest element (i.e., the value closest to 0), or negative infinity if the input was empty. For correctness, an exception should be raised when the input array is empty, since an empty array has no maximum subarray.
===Computing the best subarray's position===
The algorithm can be modified to keep track of the starting and ending indices of the maximum subarray as well.
Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem: the maximum subarray ending at the previous position) this algorithm can be viewed as a simple/trivial example of [[dynamic programming]].
===Complexity===
The runtime complexity of Kadane's algorithm is <math>O(n)</math> and its space complexity is <math>O(1)</math>.{{sfn|Bentley|1989|p=74}}{{sfn|Gries|1982|p=211}}
| |||