Max profit with unlimited trades

Question

You are given the intraday price path of a stock. Now you may complete as many trades as you want, but you can hold at most one share at a time, so you must sell before buying again. Short selling is not allowed.

prices = [7, 1, 5, 3, 6, 4]
-> 7           # buy 1 sell 5 (+4), buy 3 sell 6 (+3)

prices = [7, 6, 4, 3, 1]
-> 0           # only falls; skip every trade

Return the maximum total profit. Aim for $O(n)$ time and $O(1)$ space.

Accepted Answer

With unlimited trades the answer is simply the sum of every upward step. Capturing each consecutive rise prices[i] - prices[i-1] when it is positive is equivalent to buying at the bottom of each climb and selling at the top: a run from a local low to a local high telescopes into the sum of its daily gains. Tracing [7, 1, 5, 3, 6, 4]: the daily changes are -6, +4, -2, +3, -2, and summing the positive ones gives 4 + 3 = 7, the same as the two explicit trades above. Time O(n), space O(1). You never need to detect peaks and valleys explicitly; grabbing every positive step is cleaner and provably …

Max profit with unlimited trades

Your answer

More Coding questions