Best cumulative gain run

Question

Given a series of period returns (some negative), find the largest total achievable by any contiguous run, the best winning streak, measured by summed return.

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

Return the maximum contiguous sum. Aim for $O(n)$ .

Accepted Answer

Scan once, keeping the best sum of any run that ends at the current position. Extending the previous run is worthwhile only if that previous best was positive; otherwise start fresh at the current element. Formally, the best run ending here is max(current, previousbest + current). Track the global maximum of these values. Tracing [-2, 3, -1, 4, -10, 2]: the run-ending-here values are -2, 3, 2, 6, -4, 2; the largest is 6, from the run [3, -1, 4]. Time O(n), space O(1). Edge cases: an all-negative series correctly returns its largest single element (the least bad), because starting fresh always…

Best cumulative gain run

Your answer

More Coding questions