Kadane's algorithm
= Kadane's algorithm
{c}
For input $a_1,\ldots,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>.