Maximum-subarray segment summary ($(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 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.