Kadane's algorithm

For input $a_1,\dots ,a_n$, let $E_i$ be the largest sum of a nonempty contiguous block ending at $i$. The recurrence relation $E_1=a_1$ and $E_i=\max (a_i,E_{i-1}+a_i)$ is exact: an optimal block either starts at $i$ or extends an optimal block ending at $i-1$. The answer is ${\max }_i{E}_i$. Keeping only the current $E_i$ and best value gives linear time complexity and constant extra space complexity.