Content deleted Content added
revert to Python example code, it's much shorter and more readable (also, the pseudo-Pascal version seems buggy for one-element arrays with the sole element negative) |
m →Kadane's algorithm: note the possibility of returning the start and end indices of the maximum subarray |
||
Line 14:
return max_so_far
</source>
The algorithm can also be easily modified to keep track of the starting and ending indices of the maximum subarray.
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 example of [[dynamic programming]].
| |||