Maximum subarray problem

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

The problem was first posed by Ulf Grenander of Brown University in 1977, as a simplified model for maximum likelihood estimation of patterns in digitized images. A linear time algorithm was found soon afterwards by Jay Kadane of Carnegie Mellon University (Bentley 1984).

Kadane's algorithm begins with a simple inductive question: if we know the maximum subarray sum ending at position ${\displaystyle i}$, what is the maximum subarray sum ending at position ${\displaystyle i+1}$? The answer turns out to be relatively straightforward: either the maximum subarray sum ending at position ${\displaystyle i+1}$ includes the maximum subarray sum ending at position ${\displaystyle i}$ as a prefix, or it doesn't. Thus, we can compute the maximum subarray sum ending at position ${\displaystyle i}$ for all positions ${\displaystyle i}$ by iterating once over the array. As we go, we simply keep track of the maximum sum we've ever seen. Thus, the problem can be solved with the following code, expressed here in Python:

...
Wikipedia