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.