Challenge
Find a nonempty contiguous subarray with maximum sum. Return [sum, start, end], where the interval is nums[start:end] (end excluded). Among equal sums choose the smallest start, then the smallest end. For the exceptional empty input return [0, 0, 0].
Input and output contract
0 ≤ n ≤ 60,000; integer elements with absolute value ≤ 1,000,000. Nonempty input must produce a nonempty interval, even when every element is negative.
All tests follow this contract. You do not need to validate malformed input. Return the requested result from maximum_subarray; printed output is not your answer. Standard-library tools are allowed. Implement your solution in Python 3.12.
Target complexity: O(n) time; O(1) auxiliary space
Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.
Public examples
Arguments
[[-2, 3, -1, 3, -5]]
Expected return
[5, 1, 4]
Arguments
[[0, 0]]
Expected return
[0, 0, 1]
Arguments
[[-5, -2, -7]]
Expected return
[-2, 1, 2]
Hint
Extend the previous best suffix unless its sum is negative. Preserve a zero-sum prefix because it gives an earlier start.
The worked solution unlocks after completion, or with Premium access.