Best contiguous run of daily P&L

Question

You are given a strategy's daily profit and loss as a list (values can be negative). You want the single contiguous stretch of days that would have made the most money, holding the position from some start day through some end day. You must be in the market at least one day.

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

pnl = [-3, -1, -2]
-> -1          # every day loses; the least-bad single day

Return the maximum contiguous sum. Aim for $O(n)$ time and $O(1)$ space.

Accepted Answer

This is Kadane's algorithm, the same one-pass idea as best-single-trade. Sweep left to right holding the best sum of a run ending at the current day. At each day you either extend the previous run or start fresh from today, whichever is larger, and you track the best run seen anywhere. Tracing [-2, 1, -3, 4, -1, 2, 1, -5, 4]: the run ending at each day peaks over the stretch 4, -1, 2, 1, whose sum is 6, and no later run beats it (the final 4 cannot recover from the -5 before it). Time O(n), space O(1). In fact best-single-trade is exactly Kadane run on the vector of daily price changes, which…

Best contiguous run of daily P&L

Your answer

More Coding questions