Maximum profit by buying and selling a share at most k times

The problem, simply

You get prices, where prices[d] is the price of one share on day d, and a number k. One trade means buy once, then sell once later. You may hold at most one share at a time, so you must sell before you buy again.

Give back the most money you can make with at most k trades. If prices only fall, the answer is 0: you do not trade at all.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk day by day and try every move that is allowed today.

1. If you are free (no card): rest, or buy today (pay the price).
2. If you hold a card: rest, or sell today (get the price) and use up one trade.
3. Stop when the days run out or no trades are left.

class Solution {
    public int maxProfit(int k, int[] prices) {
        return solve(prices, 0, k, false);
    }

    private int solve(int[] prices, int day, int left, boolean holding) {
        if (day == prices.length || left == 0) return 0;
        int rest = solve(prices, day + 1, left, holding);           // do nothing today
        if (holding) {
            int sell = prices[day] + solve(prices, day + 1, left - 1, false);
            return Math.max(rest, sell);
        } else {
            int buy = -prices[day] + solve(prices, day + 1, left, true);
            return Math.max(rest, buy);
        }
    }
}

How long it takes: two choices every day, O(2^n). Extra room: one waiting call per day, O(n). The same question (same day, same trades left, same hand) comes up many times, so we should write answers down.

Way 2: the clever way

Make a table dp[t][d]: the most money by day d using at most t trades.

1. Row 0 is all 0 (no trades). Column 0 is all 0 (you cannot sell on the first day).
2. For box dp[t][d], either rest: dp[t][d - 1], or sell today. Selling today means you bought on an earlier day m, with dp[t - 1][m] money before buying. That gives dp[t - 1][m] - prices[m] + prices[d].
3. The part dp[t - 1][m] - prices[m] does not depend on today. Keep the best one so far in bestBuy, and update it as you move right.
4. The answer is the bottom right box.

Each box gets two arrows: one from the box on its left (rest) and one from the best buy day in the row above (sell).

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n <= 1 || k == 0) return 0;

        if (k >= n / 2) {                       // enough trades to catch every rise
            int profit = 0;
            for (int i = 1; i < n; i++) {
                profit += Math.max(0, prices[i] - prices[i - 1]);
            }
            return profit;
        }

        int[][] dp = new int[k + 1][n];         // row 0 and column 0 stay 0
        for (int t = 1; t <= k; t++) {
            int bestBuy = dp[t - 1][0] - prices[0];       // money left after the best buy so far
            for (int d = 1; d < n; d++) {
                dp[t][d] = Math.max(dp[t][d - 1], bestBuy + prices[d]);   // rest, or sell today
                bestBuy = Math.max(bestBuy, dp[t - 1][d] - prices[d]);     // or buy today for later
            }
        }
        return dp[k][n - 1];
    }
}

How long it takes: k rows times n days, constant work per box, O(n * k). Extra room: the table, O(n * k). Only the row above is used, so two rows of n are enough.

Watch out for

• Update bestBuy after using it for today's box, or you may buy and sell on the same day. That is harmless here (it earns 0) but it confuses people reading the code.
• Use row t - 1 for the buy money, not row t. Using row t lets one trade count twice.
• An empty price list or k = 0 gives 0.

What interviewers ask next

• Can you use O(k) memory? Yes. Keep buy[t] and sell[t] for each t and update them day by day: buy[t] = max(buy[t], sell[t - 1] - price), sell[t] = max(sell[t], buy[t] + price).
• What about a fee per trade? Subtract the fee when you sell.
• What about a one day cooldown after selling? Buy from the money of two days ago instead of yesterday.
• Is there something faster for huge n and k? Yes: list each rising run as a valley and a peak, then merge the cheapest runs until only k are left using a heap. That is O(n log n).

Remember this

Grown-up words: the notebook is a 2D DP table, the round trips are transactions, bestBuy is the running maximum that removes the inner loop, and "hold or free" is the state in a state machine DP.