Max-Sum Subarray, Then Variants

A daily PnL series is a list of signed integers. A trading desk wants to know the best run it ever had: the contiguous stretch of days with the largest total PnL.

Implement max_subarray_sum(values) returning the maximum sum over all non-empty contiguous subarrays of values.

Examples

max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4])
# 6  (the stretch [4, -1, 2, 1])

max_subarray_sum([-3, -1, -7])
# -1  (a subarray must be non-empty; the least-bad single day wins)

Constraints

• 1 <= len(values) <= 200000, values fit in a normal integer range.
• The whole list may be negative; the empty subarray is not allowed.
• Aim for a single pass; a solution that examines every subarray pair will not finish in time on the largest hidden test.

The variants

Only the function above is graded. The variants are the follow-up questions an interviewer asks once you have the sum, and they are what the title refers to. Try them in your head before you look: the Solution tab answers all four.

• Return the first and last day of the best run, not only its total.
• Take a price series instead of a PnL series, and report the largest drawdown.
• Cap the run at k days.
• Read the values one at a time, keeping nothing but your running state.