DSA

Best Time to Buy and Sell Stock - IV

Covers: Recursive, Memoized. Optimal — Time O(kn), Space O(2 * k).

August 8, 2026
DSADynamic ProgrammingDPLeetCodePractice

Practice Link

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Intiution#

At any point we have two options just keep check for the maximum possible transactions:

  1. Buy a stock (only if previously not bought)
  • Do not sell - no transaction
  • sell stock
  1. Sell a stock (only if previously bought)
  • Do not buy - no transaction
  • buy stock

Recursive Approach#

This is the generalization of Stock III with at most k transactions instead of a fixed 2. The state (idx, canBuy, transactions) drives the recursion exactly as before: at each sell we decrement transactions, and we stop when no transactions remain or all days are exhausted. Since k can be large, the uncached recursion revisits the same states repeatedly and times out.

cpp
class Solution {
public:

    int solve(vector<int> &prices, int idx, bool canBuy, int transactions)
    {
        if(transactions==0 || idx == prices.size())
            return 0;

        int profit = 0;

        if(canBuy)
            profit += max(solve(prices, idx+1, 1, transactions), -prices[idx] + solve(prices, idx+1, 0, transactions));
        else
            profit += max(solve(prices, idx+1, 0, transactions), prices[idx] + solve(prices, idx+1, 1, transactions-1));

        return profit;
    }

    int maxProfit(int k, vector<int>& prices) {
        return solve(prices, 0,1, k);
    }
};

Time Complexity: O(2^n) --> TLE

Space Complexity: O(n)

Memoized Approach#

Memoization stores already computed results in a dp array to avoid recalculations. This optimizes the recursive approach, reducing redundant computations while still exploring all possible outcomes.

cpp
class Solution {
public:

    int solve(vector<int>& prices, int idx, bool canBuy, int transactions, vector<vector<vector<int>>> &memo)
    {
        if(transactions==0 || idx==prices.size())
            return 0;

        if(memo[idx][canBuy][transactions]!=-1)
            return memo[idx][canBuy][transactions];

        int profit = 0;

        if(canBuy)
            profit += max(solve(prices, idx+1, 1, transactions, memo), -prices[idx]+solve(prices, idx+1, 0, transactions, memo));
        else    
            profit += max(solve(prices, idx+1, 0, transactions, memo), prices[idx]+solve(prices, idx+1, 1, transactions-1, memo));

        return memo[idx][canBuy][transactions] = profit;
    }

    int maxProfit(int k, vector<int>& prices) {
        vector<vector<vector<int>>> memo(prices.size(), vector<vector<int>>(2, vector<int>(k+1, -1)));
        return solve(prices, 0, 1, k, memo);
    }
};

Time Complexity: O(2 * k * n) ~ O(kn)

Space Complexity: O(2 * k * n) + O(kn) (Recursive stack)

Tabulation#

Build a 3D table dp[idx][canBuy][t] iterating from the last day back to day 0, with each cell computed in O(1) from the next day's row. The total states are n × 2 × (k+1), so overall time is O(kn) and space is O(kn). By going bottom-up we remove the call-stack overhead of memoization.

cpp
class Solution {
public:

    int maxProfit(int k, vector<int>& prices) {
        vector<vector<vector<int>>> dp(prices.size()+1, vector<vector<int>>(2, vector<int>(k+1, 0)));

        for(int idx = prices.size()-1;idx>=0;idx--)
        {
            for(int canBuy=0;canBuy<=1;canBuy++)
            {
                for(int t = 1;t<=k;t++)
                {
                    int profit=0;
                    if(canBuy)
                        profit = max(dp[idx+1][1][t], -prices[idx]+dp[idx+1][0][t]);
                    else    
                        profit = max(dp[idx+1][0][t], prices[idx]+dp[idx+1][1][t-1]);

                    dp[idx][canBuy][t] = profit;
                }
            }
        }
        return dp[0][1][k];
    }
};

Time Complexity: O(2 * k * n) ~ O(kn)

Space Complexity: O(2 * k * n)

Space Optimized Tabulation#

Each day's row depends only on the next day's row, so we keep two 2D arrays — next (size 2 × (k+1)) and curr — and swap them after each day. Space collapses from O(2kn) to O(2k) while time stays O(kn).

cpp
class Solution {
public:

    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> next(2, vector<int>(k+1, 0));
        vector<vector<int>> curr(2, vector<int>(k+1, 0));

        for(int idx = prices.size()-1;idx>=0;idx--)
        {
            for(int canBuy=0;canBuy<=1;canBuy++)
            {
                for(int t = 1;t<=k;t++)
                {
                    int profit=0;
                    if(canBuy)
                        profit = max(next[1][t], -prices[idx]+next[0][t]);
                    else    
                        profit = max(next[0][t], prices[idx]+next[1][t-1]);

                    curr[canBuy][t] = profit;
                    next = curr;
                }
            }
        }
        return next[1][k];
    }
};

Time Complexity: O(2 * k * n) ~ O(kn)

Space Complexity: O(2 * k)

Related articles

DSALongest Common Prefix5 approaches incl. Horizontal Scanning, Vertical Scanning, Binary Search, and more. Optimal — Time O(s log m), Space O(1).DSAMaximum Subarray SumCovers: Brute Force, Optimal. Optimal — Time O(n), Space O(1).DSAPalindromic SubstringCovers: Brute Force: generate all su…, Expansion on center, DP. Optimal — Time O(n<sup>2</sup>), Space O(n<sup>2</sup>).