Maximum subarray problem

Given a finite sequence of real numbers, find a nonempty contiguous block with maximum sum. Its restriction to contiguous blocks distinguishes it from choosing an arbitrary subset. The problem admits a linear-time solution using Kadane's algorithm.

For a segment, store its total sum $S$, maximum possibly-empty prefix sum $P$, maximum possibly-empty suffix sum $Q$ and maximum possibly-empty internal contiguous sum $B$. Adjacent segment summaries combine byA prefix either stays on the left or includes the whole left segment and a right prefix. A suffix has the symmetric decomposition. An internal segment either stays in one child or crosses the boundary as a left suffix followed by a right prefix. These cases prove the formulas, including empty candidates. Store the corresponding endpoints to recover a winning segment. This constant-size summary gives a linear time divide-and-conquer algorithm for the empty-allowed maximum subarray problem.

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.