Best contiguous stretch of daily returns

Question

Given a strategy's daily PnL (positive and negative), find the single contiguous stretch of days with the largest total. You must pick consecutive days, no cherry-picking.

returns = [3, -4, 5, -1, 2, -6, 4]
-> 6        # the run [5, -1, 2]

Return the maximum sum of any contiguous subarray in O(n) time and O(1) space.

Accepted Answer

Sweep left to right carrying cur, the best sum of a run that ends at the current day. At each day you either start fresh with today's value or extend the previous run, whichever is larger: cur = max(r, cur + r). The moment cur would go negative, it is better to reset. Track the best cur ever seen. Tracing [3, -4, 5, -1, 2, -6, 4]: cur goes 3, -1, 5, 4, 6, 0, 4 and best climbs to 6 at the [5, -1, 2] run. Time O(n), space O(1). Edge cases: if every day loses money, this returns the single least-bad day (never an empty window); to also report the start/end, remember the index where the current r…

Best contiguous stretch of daily returns

Your answer

More Coding questions