Content deleted Content added
complexity belongs before the formalization and discussion |
|||
Line 150:
In Python, arrays are indexed starting from 0, and slices exclude the endpoint, so that the subarray [22, 33] in the array a=[-11, 22, 33, -44] would be expressed as a[1:3].
===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]].
▲===Complexity===
The runtime complexity of Kadane's algorithm is <math>O(n)</math>.{{sfn|Bentley|1989|p=74}}{{sfn|Gries|1982|p=211}}
| |||