Best Time to Buy and Sell Stock IV

Hard20–25 min

Topics

Dynamic Programming

Companies

GoogleAmazonMicrosoft

Given daily stock `prices` and a transaction limit `k`, complete at most `k` buy-sell transactions — never holding more than one share, and always selling before buying again. Maximize total profit; `k = 0` always yields 0. This is the two-transaction problem stretched to an arbitrary count: instead of four named variables for buy1/sell1/buy2/sell2, keep two arrays of length k+1, `buy[t]` and `sell[t]`, one pair of slots per transaction number. Sweeping through the prices once, and inside that updating slot 1 through slot k in order, `buy[t]` only ever reads `sell[t-1]` — the profit already locked in by finishing the transaction before it — so every slot is always built from information that's already settled for the current day before it's needed.

Test Case 1:

Input:k = 2, prices = [2,4,1]

Output:2

Explanation:Buy at 2 (day 0), sell at 4 (day 1) for 2 — the only profitable move here, and the second transaction never gets used.

Test Case 2:

Input:k = 2, prices = [3,2,6,5,0,3]

Output:7

Explanation:Buy at 2 (day 1), sell at 6 (day 2) for 4, then buy at 0 (day 4), sell at 3 (day 5) for 3 — two transactions totaling 7.

Test Case 3:

Input:k = 0, prices = [1,2,3]

Output:0

Explanation:Zero allowed transactions means no trade can ever happen, no matter how the prices move — the answer is always 0.

Constraints

◆0 ≤ k ≤ 5
◆1 ≤ prices.length ≤ 10
◆0 ≤ prices[i] ≤ 1000
◆at most k buy-sell transactions are allowed; you must sell before buying again

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Generalize the single-transaction decision to a running counter of transactions still available: at every day, either skip it, or (if not holding) spend one of the remaining transaction slots to buy, or (if holding) spend nothing extra and sell to close out a slot. Recursing over both choices at every day covers every possible sequence of up to k transactions, but the same (day, holding, transactions-remaining) situation gets rediscovered on many different branches with no memory of earlier work.

TimeO(2ⁿ)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] prices;

    public int maxProfit(int k, int[] prices) {
        this.prices = prices;
        return solve(0, false, k);
    }

    private int solve(int day, boolean holding, int txnsLeft) {
        if (day == prices.length || txnsLeft == 0) return 0;
        int doNothing = solve(day + 1, holding, txnsLeft);
        int act;
        if (holding) {
            act = prices[day] + solve(day + 1, false, txnsLeft - 1);
        } else {
            act = -prices[day] + solve(day + 1, true, txnsLeft);
        }
        return Math.max(doNothing, act);
    }
}

Optimal — k-Transaction State Arrays

Optimal

Stretch the four-variable pattern used for two transactions into a pair of arrays sized k+1: buy[t] is the best result after opening the t-th position, sell[t] the best result after closing it. Sweeping through the prices once, transaction slot 1 through k in order at every day, each buy[t] only ever needs sell[t-1] — the profit already banked from finishing the transaction before it — so by the time slot t is updated everything it depends on is already correct for that day.

TimeO(n · k)

SpaceO(k)