Content deleted Content added
→top: not sure that max_{i,j}E(i,j) is appropriately (i.e. yielding pairs (i,j)) defined anywhere; suggest to paraphrase it in English again |
Pharlan35244 (talk | contribs) |
||
Line 87:
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> (it is actually theta(n) because both the lower bound and the upper bound has the same runtime. By saying it is O(n) you are state that the lower bound differs from the upper bound, thus it is incorrect for the run time to be <math>O(n)</math>).
== Generalizations ==
| |||