= Maximum-subarray segment summary
{title2=$(S,P,Q,B)$}
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 by
$$
(S,P,Q,B)=\left(S_L+S_R,\ \max(P_L,S_L+P_R),\ \max(Q_R,S_R+Q_L),\ \max(B_L,B_R,Q_L+P_R)\right).
$$
A 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>.
Back to article page
