Maximum subarray problem: Difference between revisions

Revision as of 15:17, 5 March 2023

Revision as of 15:20, 5 March 2023

Line 75:

This version of the algorithm will return 0 if the input contains no positive elements (including when the input is empty).

The algorithm can be adapted to the case which disallows empty subarrays or to keep track of the starting and ending indices of the maximum subarray. as well:

Because of the way thisThis algorithm uses optimal substructurescalculates (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), thisso algorithmit can be viewed as a simple/trivial examplecase 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}}

== Generalizations ==