Max-Sum Subarray, Then Variants

A daily PnL series is a sequence 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, which returns the maximum sum over all non-empty contiguous subarrays of values.

long long max_subarray_sum(const std::vector<long long>& 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 <= values.size() <= 2000000, and every sum fits in a long long.
• The whole series may be negative; the empty subarray is not allowed.
• Aim for a single pass. A solution that examines every pair of start and end days 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 five.

• 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.
• Take a price series and return the most one trade could make: buy on one day, sell on a later day, or 0 when no trade makes money.