Maximum subarray problem: Difference between revisions

Revision as of 02:11, 26 February 2023

Revision as of 03:03, 26 February 2023

Line 149:

===Complexity===

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]].

The runtime complexity of Kadane's algorithm is <math>O(n)</math>.{{sfn|Bentley|1989|p=74}}{{sfn|Gries|1982|p=211}}