Topics › Dynamic Programming › DP on Stocks

Best time to buy and sell stock II

Medium TUF ID 302 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

prices[i] is the price of a stock on day i. You may make as many transactions as you like, with one restriction: you can hold at most one share at a time, so you must sell before you buy again. Selling and buying on the same day is allowed but never helps. Return the maximum total profit.

Constraints: 1 ≤ n ≤ 3 × 10^4, 0 ≤ prices[i] ≤ 10^4. The total profit is at most about 3 × 10^8, so int is enough.

Example 1

prices = [7, 1, 5, 3, 6, 4]
answer = 7          // buy 1, sell 5 (+4); buy 3, sell 6 (+3)

Example 2

prices = [1, 2, 3, 4, 5]
answer = 4          // buy 1, sell 5; or four one-day trades, same total

Compared with the single-transaction problem, the difficulty is that each decision (buy now or wait, sell now or hold) changes what is possible later. That is exactly the situation DP handles: define a state that captures everything the future depends on.

Approach 1: Recursion

Intuition. Walk through the days in order. On day i, the only facts that matter for the rest of the game are the day index and whether we currently hold a share. The past prices do not matter once their money is in the balance. So let f(i, canBuy) be the best profit obtainable from day i to the end:

• If canBuy = 1 (no share held): either buy today, paying prices[i] and moving to f(i + 1, 0), or skip to f(i + 1, 1).
• If canBuy = 0 (holding a share): either sell today, receiving prices[i] and moving to f(i + 1, 1), or hold, f(i + 1, 0).
• Base case: f(n, *) = 0. A share still held at the end is worth nothing, so a plan that ends holding is always beaten (or tied) by the same plan without its last buy. The maximum therefore never needs a special rule against it.

Treating a buy as -prices[i] and a sell as +prices[i] means the profit of a trade is accumulated automatically; we never need to remember the buy price.

Algorithm.

1. If i == n, return 0.
2. If canBuy, return max(-prices[i] + f(i+1, 0), f(i+1, 1)).
3. Otherwise return max(prices[i] + f(i+1, 1), f(i+1, 0)).
4. The answer is f(0, 1).

static int recursive(int[] prices) {
    return solve(0, 1, prices);
}

static int solve(int i, int canBuy, int[] prices) {
    if (i == prices.length) return 0;
    if (canBuy == 1) {
        return Math.max(-prices[i] + solve(i + 1, 0, prices),     // buy today
                        solve(i + 1, 1, prices));                 // skip
    }
    return Math.max(prices[i] + solve(i + 1, 1, prices),          // sell today
                    solve(i + 1, 0, prices));                     // keep holding
}

Complexity. Time O(2^n): each call branches twice. Space O(n) recursion depth.

Approach 2: Memoization

Intuition. There are only 2n distinct states (i, canBuy), but the recursion visits them exponentially many times. Store each answer the first time it is computed. Every profit value is at least 0, so -1 is a safe “not computed” marker.

Algorithm. Same recurrence, with a lookup in dp[i][canBuy] before computing and a store after.

static int memoization(int[] prices) {
    int[][] dp = new int[prices.length][2];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(0, 1, prices, dp);
}

static int memo(int i, int canBuy, int[] prices, int[][] dp) {
    if (i == prices.length) return 0;
    if (dp[i][canBuy] != -1) return dp[i][canBuy];
    int best;
    if (canBuy == 1) best = Math.max(-prices[i] + memo(i + 1, 0, prices, dp), memo(i + 1, 1, prices, dp));
    else best = Math.max(prices[i] + memo(i + 1, 1, prices, dp), memo(i + 1, 0, prices, dp));
    return dp[i][canBuy] = best;
}

Complexity. Time O(n): 2n states, O(1) work each. Space O(n) for the table plus O(n) stack. For n = 3 × 10^4 the recursion depth can exceed Java’s default stack, which is a practical reason to move to tabulation.

Approach 3: Tabulation

Intuition. f(i, *) depends only on f(i + 1, *), so fill the table from i = n - 1 down to 0. Row n is all zeros, which Java gives for free.

Algorithm.

1. Create dp[n + 1][2], all zero.
2. For i from n - 1 down to 0, fill dp[i][1] and dp[i][0] with the two formulas.
3. Return dp[0][1].

static int tabulation(int[] prices) {
    int n = prices.length;
    int[][] dp = new int[n + 1][2];                     // dp[n][*] = 0: no days left
    for (int i = n - 1; i >= 0; i--) {
        dp[i][1] = Math.max(-prices[i] + dp[i + 1][0], dp[i + 1][1]);
        dp[i][0] = Math.max(prices[i] + dp[i + 1][1], dp[i + 1][0]);
    }
    return dp[0][1];
}

Dry run on prices = [7, 1, 5, 3, 6, 4] (columns are dp[i][1] = free to buy, dp[i][0] = holding):

The answer is dp[0][1] = 7. (dp[0][0] = 14 would be the profit if we were somehow already holding a share for free on day 0.)

Complexity. Time O(n), space O(n).

Approach 4: Space optimised

Intuition. Each row reads only the row below it, so two variables, aheadBuy = dp[i+1][1] and aheadHold = dp[i+1][0], replace the table. Compute both new values into temporaries before overwriting, because each formula needs the old value of the other.

static int spaceOptimized(int[] prices) {
    int aheadBuy = 0, aheadHold = 0;                    // dp[i + 1][1], dp[i + 1][0]
    for (int i = prices.length - 1; i >= 0; i--) {
        int buy = Math.max(-prices[i] + aheadHold, aheadBuy);
        int hold = Math.max(prices[i] + aheadBuy, aheadHold);
        aheadBuy = buy;
        aheadHold = hold;
    }
    return aheadBuy;
}

Complexity. Time O(n), space O(1).

Approach 5: Greedy

Intuition. With unlimited transactions, any rise from one day to the next can be captured. A long rise from a to b equals the sum of its daily steps, so splitting a trade into one-day trades never loses profit, and skipping a falling day never hurts. Therefore the answer is the sum of all positive differences prices[i] - prices[i - 1].

This shortcut exists only because there is no limit and no cost per trade. As soon as trades are limited (Stock III and IV), have a fee, or have a cooldown, splitting a trade changes the cost, and we need the DP again. That is why the DP formulation is the one worth mastering here.

static int greedy(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
    }
    return profit;
}

Complexity. Time O(n), space O(1).

Edge cases and pitfalls

• One day or no days. No trade can complete; every method returns 0.
• Falling prices. The best plan is to never buy, so the answer is 0; the “skip” branch guarantees this.
• Order of updates in the space optimised loop. Writing aheadBuy first and then using it to compute aheadHold mixes day i with day i + 1. In this particular problem the mix happens to give the same answer (it corresponds to a same-day buy and sell), but in the cooldown and fee variants that habit causes bugs, so always use temporaries.
• Holding at the end. The base case returns 0 for both states. You do not need a special rule forbidding an unsold share; the maximum never prefers it.
• Recursion depth. Memoization recurses n levels deep; for large n prefer tabulation or the O(1) version.

Related problems

• Best time to buy and sell stock is the one-transaction version.
• Best time to buy and sell stock III adds a third state dimension for the number of transactions left.
• Best Time to Buy and Sell Stock with Cooldown changes the sell transition to jump two days.
• Best time to buy and sell stock with transaction fees subtracts a fee on every sell.
• Introduction to DP explains the recursion to tabulation to space optimisation pipeline used here.