Start practising

Best Time to Buy and Sell Stock II

Medium Dynamic Programming State Machine DP - Stock Problems Original on LeetCode

Best Time to Buy and Sell Stock II is a medium dynamic programming problem solved with the state machine dp - stock problems pattern. The best approach, greedy (sum every rise), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from state machine dp up.

Problem

Same prices, but now you may make as many transactions as you like. You can hold at most one share at a time (sell before you buy again). Return the maximum profit.

Examples

Example 1

Input
prices = [7, 1, 5, 3, 6, 4]
Output
7
Why
Buy 1 sell 5 (+4), buy 3 sell 6 (+3).

Example 2

Input
prices = [1, 2, 3, 4, 5]
Output
4

Constraints

  • 1 <= prices.length <= 3 * 10^4.
  • Unlimited transactions, holding at most one share at a time.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
State machine DPO(n)O(1)
Greedy (sum every rise)O(n)O(1)

1State machine DP

TimeO(n)
SpaceO(1)

hold = best profit while holding a share; free = best profit while not holding. Each day: hold = max(hold, free - price); free = max(free, hold + price).

  1. hold = -prices[0], free = 0.
  2. Update both each day (use the old hold when computing free).
Java
class Solution {
    public int maxProfit(int[] prices) {
        int hold = -prices[0], free = 0;
        for (int i = 1; i < prices.length; i++) {
            int newHold = Math.max(hold, free - prices[i]);
            free = Math.max(free, hold + prices[i]);
            hold = newHold;
        }
        return free;
    }
}

2Greedy (sum every rise)

TimeO(n)
SpaceO(1)

Any profitable stretch can be split into day-to-day rises. Collecting every positive difference gives the same total.

  1. profit += max(0, prices[i] - prices[i - 1]).
Java
class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) profit += Math.max(0, prices[i] - prices[i - 1]);
        return profit;
    }
}

Edge cases to test

  • Strictly falling prices (0)

Hints

Hint 1

Two states each day: holding a share or not. Or: every upward step can be collected.

FAQ

What is the best time complexity for Best Time to Buy and Sell Stock II?

Greedy (sum every rise) runs in O(n) time and O(1) extra space.

Which pattern does Best Time to Buy and Sell Stock II use?

It is a dynamic programming problem that uses the state machine dp - stock problems pattern. Other problems with the same pattern: Best Time to Buy and Sell Stock, Best Time to Buy and Sell Stock with Transaction Fee, Best Time to Buy and Sell Stock with Cooldown.

Is there a brute force solution for Best Time to Buy and Sell Stock II?

Yes. State machine DP takes O(n) time and O(1) space. hold = best profit while holding a share; free = best profit while not holding.

Which edge cases should I test for Best Time to Buy and Sell Stock II?

Strictly falling prices (0).