= Solution
Let $e_i$ be the best sum of a segment ending at position $i$, allowing the empty segment with sum zero. The <maximum subarray problem> recurrence is
$$
\boxed{e_0=0,\qquad e_i=\max(0,e_{i-1}+a_i),\qquad B_i=\max(B_{i-1},e_i),\ B_0=0.}
$$
An optimal nonempty segment ending at $i$ extends the best suffix ending at $i-1$, or starts fresh; a negative suffix cannot help. Keep its start index and record endpoints whenever a new overall best is found:
``
suffix = 0; best = 0
start = 0; bestLeft = 0; bestRight = 0
for i = 0,...,n-1:
suffix = suffix + A[i]
if suffix < 0:
suffix = 0; start = i+1
if suffix > best:
best = suffix
bestLeft = start; bestRight = i+1
return A[bestLeft:bestRight]
``
The half-open endpoint interval is empty initially, so empty input and all-negative input correctly return an empty segment. The invariant identifies the best nonnegative suffix and the best segment in the scanned prefix, proving correctness. This is <Kadane's algorithm>, using \b[$O(n)$ time and $O(1)$ auxiliary space], excluding the returned slice. The displayed example yields \b[sum $55$], from the segment $10,-5,40,10$.
Back to article page
