Content deleted Content added
→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 |
→No empty subarrays admitted: nonempty |
||
Line 82:
|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 nonempty 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.
| |||