 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 isAn 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 $O(n)$ time and $O(1)$ auxiliary space, excluding the returned slice. The displayed example yields sum $55$, from the segment $10,-5,40,10$.