Kadane's algorithm

Let $f(i)$ be the maximum subarray sum that ends exactly at index $i$.

Now, the answer to the maximum subarray problem is just

History tidbit

The optimal solution above looks like something one could come up with on the spot, which does not seem to be the case for most. But that is exactly how the solution was actually proposed.

In 1977, Ulf Grenander at Brown University formalised this problem when he encountered it as a step in solving a different problem involving images. He proposed an $O(n^3)$ solution, later improving it to $O(n^2)$.

When Michael Shamos heard about the problem, he came up with an $O(n \log n)$ divide-and-conquer solution overnight (at least according to Wikipedia). When Shamos presented the history of this problem at a lecture at CMU, Jay Kadane, a statistician in a room full of computer scientists, proposed the $O(n)$ solution on the spot.