188. Best Time to Buy and Sell Stock IV Solution

The problem

You are given an integer array prices where prices[i] is the price of a given stock on the i^th 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).

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Constraints:

1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000

Approach overview

Problem Overview: You receive an array prices where prices[i] is the stock price on day i. You may complete at most k buy-sell transactions. Each transaction consists of buying once and selling once. The goal is to compute the maximum profit while respecting the transaction limit.

Approach 1: State-based Dynamic Programming (O(nk) time, O(nk) space)

This method models the problem using explicit DP states. Let dp[t][i] represent the maximum profit achievable using at most t transactions up to day i. For each day, you decide whether to skip trading or sell the stock, which requires tracking the best previous buy opportunity. While iterating through days, maintain a running value like maxDiff = max(dp[t-1][j] - prices[j]) to efficiently compute profits. The approach systematically fills the DP table and clearly illustrates the transaction transitions, making it useful for understanding the classic dynamic programming formulation.

Approach 2: Dynamic Programming with State Compression (O(nk) time, O(k) space)

The DP table can be compressed because each transaction state depends only on the previous transaction layer. Maintain two arrays: buy[t] and sell[t]. buy[t] tracks the best profit after buying for the t-th transaction, and sell[t] tracks the best profit after selling. Iterate through the prices array and update these states sequentially for each transaction count. This reduces memory from O(nk) to O(k) while preserving the same recurrence, making it the preferred implementation in production or interviews. The iteration simply processes each price and updates transaction states using constant-time transitions.

Approach 3: Greedy Optimization for Large k (O(n) time, O(1) space)

If k >= n/2, the constraint effectively disappears because you can perform unlimited transactions. In this case, the optimal strategy is to sum every positive price difference between consecutive days. Iterate once through the array and accumulate max(0, prices[i] - prices[i-1]). This converts the problem into the classic unlimited transaction variant from stock trading problems and avoids unnecessary array DP processing.

Recommended for interviews: Interviewers usually expect the dynamic programming formulation with transaction states. Explaining the full DP table shows understanding of the recurrence. Implementing the state-compressed version demonstrates stronger optimization skills and familiarity with advanced dynamic programming patterns.

Approach 1: Dynamic Programming with State Compression

This approach involves using a dynamic programming table where dp[i][j] represents the maximum profit obtainable on the i^th day with up to j transactions. The state can be compressed by keeping track of two main variables: one for the max profit holding deals and one for not holding deals.

Python

def maxProfit(k, prices):
    if not prices:
        return 0
    n = len(prices)
    if k >= n // 2:
        return sum(max(prices[i] - prices[i - 1], 0) for i in range(1, n))
    profits = [0] * n
    for j in range(k):
        prev_profit = 0
        max_diff = -prices[0]
        for i in range(1, n):
            temp = profits[i]
            profits[i] = max(profits[i - 1], prices[i] + max_diff)
            max_diff = max(max_diff, prev_profit - prices[i])
            prev_profit = temp
    return profits[-1]

Java

public class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++)
                profit += Math.max(0, prices[i] - prices[i - 1]);
            return profit;
        }
        int[] profits = new int[n];
        for (int j = 0; j < k; j++) {
            int maxDiff = -prices[0];
            int prevProfit = 0;
            for (int i = 1; i < n; i++) {
                int temp = profits[i];
                profits[i] = Math.max(profits[i - 1], prices[i] + maxDiff);
                maxDiff = Math.max(maxDiff, prevProfit - prices[i]);
                prevProfit = temp;
            }
        }
        return profits[n - 1];
    }
}

C++

#include <vector>
#include <iostream>
using namespace std;

int maxProfit(int k, vector<int>& prices) {
    int n = prices.size();
    if (prices.empty()) return 0;
    if (k >= n / 2) {
        int total_profit = 0;
        for (int i = 1; i < n; i++)
            total_profit += max(0, prices[i] - prices[i - 1]);
        return total_profit;
    }
    vector<int> profits(n, 0);
    for (int j = 0; j < k; j++) {
        int prev_profit = 0, max_diff = -prices[0];
        for (int i = 1; i < n; i++) {
            int temp = profits[i];
            profits[i] = max(profits[i - 1], prices[i] + max_diff);
            max_diff = max(max_diff, prev_profit - prices[i]);
            prev_profit = temp;
        }
    }
    return profits[n - 1];
}

public class Solution {
    public int MaxProfit(int k, int[] prices) {
        int n = prices.Length;
        if (n == 0) return 0;
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++)
                profit += Math.Max(0, prices[i] - prices[i - 1]);
            return profit;
        }
        int[] profits = new int[n];
        for (int j = 0; j < k; j++) {
            int maxDiff = -prices[0];
            int prevProfit = 0;
            for (int i = 1; i < n; i++) {
                int temp = profits[i];
                profits[i] = Math.Max(profits[i - 1], prices[i] + maxDiff);
                maxDiff = Math.Max(maxDiff, prevProfit - prices[i]);
                prevProfit = temp;
            }
        }
        return profits[n - 1];
    }
}

We initiate with a check for empty prices array and then determine if we are allowed more transactions than needed for continuous buying and selling. If not, proceed with a reduced number of dynamic programming states constrained by the number of transactions. We update profits using previous profits and manage maximum price differences dynamically.

Complexity

Time Complexity: O(kn), where n is the number of days and k is the number of allowed transactions.
Space Complexity: O(n), as we are storing profit states for each day.

Try this approach in the editor

Approach 2: State-based Dynamic Programming

This method is a classical dynamic programming solution where we maintain a 2D array dp[j][i], that contains the maximum profit achievable having executed up to j transactions on the i^th day.

JavaScript

function maxProfit(k, prices) {
    if (prices.length === 0) return 0;
    if (k >= Math.floor(prices.length / 2)) {
        let totalProfit = 0;
        for (let i = 1; i < prices.length; i++) {
            totalProfit += Math.max(0, prices[i] - prices[i - 1]);
        }
        return totalProfit;
    }
    const dp = Array.from({ length: k + 1 }, () => Array(prices.length).fill(0));
    for (let j = 1; j <= k; j++) {
        let maxDiff = -prices[0];
        for (let i = 1; i < prices.length; i++) {
            dp[j][i] = Math.max(dp[j][i - 1], prices[i] + maxDiff);
            maxDiff = Math.max(maxDiff, dp[j - 1][i] - prices[i]);
        }
    }
    return dp[k][prices.length - 1];
}

#include <stdlib.h>
#include <string.h>

int maxProfit(int k, int* prices, int pricesSize) {
    if (pricesSize == 0) return 0;
    if (k >= pricesSize / 2) {
        int profit = 0;
        for (int i = 1; i < pricesSize; ++i)
            profit += prices[i] > prices[i - 1] ? prices[i] - prices[i - 1] : 0;
        return profit;
    }
    int **dp = (int**)malloc((k + 1) * sizeof(int*));
    for (int i = 0; i <= k; ++i)
        dp[i] = (int*)calloc(pricesSize, sizeof(int));
    for (int j = 1; j <= k; ++j) {
        int maxDiff = -prices[0];
        for (int i = 1; i < pricesSize; ++i) {
            dp[j][i] = fmax(dp[j][i - 1], prices[i] + maxDiff);
            maxDiff = fmax(maxDiff, dp[j - 1][i] - prices[i]);
        }
    }
    int result = dp[k][pricesSize - 1];
    for (int i = 0; i <= k; ++i) free(dp[i]);
    free(dp);
    return result;
}

Utilizes a 2D array dynamically allocated for handling transaction evaluations, updating them continuously using previous transaction values and price differences for optimal profit assessment.

Complexity

Time Complexity: O(kn).
Space Complexity: O(kn), requires a separate 2D array to store states.

Try this approach in the editor

Approach 3: Memoization Search

We design a function dfs(i, j, k) to represent the maximum profit that can be obtained when starting from day i, completing at most j transactions, and holding the stock with the current state k (not holding the stock is represented by 0, and holding the stock is represented by 1). The answer is dfs(0, k, 0).

The execution logic of the function dfs(i, j, k) is as follows:

If i is greater than or equal to n, return 0 directly.
The i-th day can choose not to do anything, then dfs(i, j, k) = dfs(i + 1, j, k).
If k > 0, the i-th day can choose to sell the stock, then dfs(i, j, k) = max(dfs(i + 1, j - 1, 0) + prices[i], dfs(i + 1, j, k)).
Otherwise, if j > 0, the i-th day can choose to buy the stock, then dfs(i, j, k) = max(dfs(i + 1, j - 1, 1) - prices[i], dfs(i + 1, j, k)).

The value of dfs(i, j, k) is the maximum value of the above three cases.

During the process, we can use memoization search to save the results of each calculation to avoid repeated calculations.

The time complexity is O(n times k), and the space complexity is O(n times k), where n and k are the length of the prices array and the value of k, respectively.

TypeScript

function maxProfit(k: number, prices: number[]): number {
    const n = prices.length;
    const f = Array.from({ length: n }, () =>
        Array.from({ length: k + 1 }, () => Array.from({ length: 2 }, () => -1)),
    );
    const dfs = (i: number, j: number, k: number): number => {
        if (i >= n) {
            return 0;
        }
        if (f[i][j][k] !== -1) {
            return f[i][j][k];
        }
        let ans = dfs(i + 1, j, k);
        if (k) {
            ans = Math.max(ans, prices[i] + dfs(i + 1, j, 0));
        } else if (j) {
            ans = Math.max(ans, -prices[i] + dfs(i + 1, j - 1, 1));
        }
        return (f[i][j][k] = ans);
    };
    return dfs(0, k, 0);
}

func maxProfit(k int, prices []int) int {
	n := len(prices)
	f := make([][][2]int, n)
	for i := range f {
		f[i] = make([][2]int, k+1)
		for j := range f[i] {
			f[i][j] = [2]int{-1, -1}
		}
	}
	var dfs func(i, j, k int) int
	dfs = func(i, j, k int) int {
		if i >= n {
			return 0
		}
		if f[i][j][k] != -1 {
			return f[i][j][k]
		}
		ans := dfs(i+1, j, k)
		if k > 0 {
			ans = max(ans, prices[i]+dfs(i+1, j, 0))
		} else if j > 0 {
			ans = max(ans, -prices[i]+dfs(i+1, j-1, 1))
		}
		f[i][j][k] = ans
		return ans
	}
	return dfs(0, k, 0)
}

Try this approach in the editor

Approach 4: Dynamic Programming

We can also use dynamic programming to define f[i][j][k] as the maximum profit that can be obtained when completing at most j transactions (here we define the number of transactions as the number of purchases), and holding the stock with the current state k on the i-th day. The initial value of f[i][j][k] is 0. The answer is f[n - 1][k][0].

When i = 0, the stock price is prices[0]. For any j \in [1, k], we have f[0][j][1] = -prices[0], which means buying the stock on the 0-th day with a profit of -prices[0].

When i > 0:

If the i-th day does not hold the stock, it may be that the stock was held on the i-1-th day and sold on the i-th day, or the stock was not held on the i-1-th day and no operation was performed on the i-th day. Therefore, f[i][j][0] = max(f[i - 1][j][1] + prices[i], f[i - 1][j][0]).
If the i-th day holds the stock, it may be that the stock was not held on the i-1-th day and bought on the i-th day, or the stock was held on the i-1-th day and no operation was performed on the i-th day. Therefore, f[i][j][1] = max(f[i - 1][j - 1][0] - prices[i], f[i - 1][j][1]).

Therefore, when i > 0, we can get the state transition equation:

\begin{aligned} f[i][j][0] &= max(f[i - 1][j][1] + prices[i], f[i - 1][j][0]) \ f[i][j][1] &= max(f[i - 1][j - 1][0] - prices[i], f[i - 1][j][1]) \end{aligned}

The final answer is f[n - 1][k][0].

The time complexity is O(n times k), and the space complexity is O(n times k), where n and k are the length of the prices array and the value of k, respectively.

We notice that the state f[i][] only depends on the state f[i - 1][], so we can optimize the first dimension of the space and reduce the space complexity to O(k)$.

TypeScript

function maxProfit(k: number, prices: number[]): number {
    const n = prices.length;
    const f = Array.from({ length: n }, () =>
        Array.from({ length: k + 1 }, () => Array.from({ length: 2 }, () => 0)),
    );
    for (let j = 1; j <= k; ++j) {
        f[0][j][1] = -prices[0];
    }
    for (let i = 1; i < n; ++i) {
        for (let j = 1; j <= k; ++j) {
            f[i][j][0] = Math.max(f[i - 1][j][1] + prices[i], f[i - 1][j][0]);
            f[i][j][1] = Math.max(f[i - 1][j - 1][0] - prices[i], f[i - 1][j][1]);
        }
    }
    return f[n - 1][k][0];
}

func maxProfit(k int, prices []int) int {
	n := len(prices)
	f := make([][][2]int, n)
	for i := range f {
		f[i] = make([][2]int, k+1)
	}
	for j := 1; j <= k; j++ {
		f[0][j][1] = -prices[0]
	}
	for i := 1; i < n; i++ {
		for j := 1; j <= k; j++ {
			f[i][j][0] = max(f[i-1][j][1]+prices[i], f[i-1][j][0])
			f[i][j][1] = max(f[i-1][j-1][0]-prices[i], f[i-1][j][1])
		}
	}
	return f[n-1][k][0]
}

Try this approach in the editor

Approach 5: Default Approach

TypeScript

function maxProfit(k: number, prices: number[]): number {
    const f = Array.from({ length: k + 1 }, () => Array.from({ length: 2 }, () => 0));
    for (let j = 1; j <= k; ++j) {
        f[j][1] = -prices[0];
    }
    for (const x of prices.slice(1)) {
        for (let j = k; j; --j) {
            f[j][0] = Math.max(f[j][1] + x, f[j][0]);
            f[j][1] = Math.max(f[j - 1][0] - x, f[j][1]);
        }
    }
    return f[k][0];
}

func maxProfit(k int, prices []int) int {
	f := make([][2]int, k+1)
	for j := 1; j <= k; j++ {
		f[j][1] = -prices[0]
	}
	for _, x := range prices[1:] {
		for j := k; j > 0; j-- {
			f[j][0] = max(f[j][1]+x, f[j][0])
			f[j][1] = max(f[j-1][0]-x, f[j][1])
		}
	}
	return f[k][0]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with State Compression	Time Complexity: O(kn), where n is the number of days and k is the number of allowed transactions. Space Complexity: O(n), as we are storing profit states for each day.
State-based Dynamic Programming	Time Complexity: O(kn). Space Complexity: O(kn), requires a separate 2D array to store states.
Memoization Search	–
Dynamic Programming	–
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
State-based Dynamic Programming	O(nk)	O(nk)	Best for understanding the full DP transition and building intuition
DP with State Compression	O(nk)	O(k)	Optimal solution used in interviews and competitive programming
Greedy (Unlimited Transactions Case)	O(n)	O(1)	When k >= n/2, reducing the problem to unlimited trades

Frequently asked questions

Is Best Time to Buy and Sell Stock IV easy or hard?

Best Time to Buy and Sell Stock IV is categorized as Hard because it requires understanding multi-transaction stock trading patterns and optimizing dynamic programming states. The challenge comes from handling the transaction limit efficiently.

Best Time to Buy and Sell Stock IV Python/Java solution

Python and Java implementations typically maintain two arrays: buy and sell. For each price, update buy[t] = max(buy[t], sell[t-1] - price) and sell[t] = max(sell[t], buy[t] + price). This state-compressed DP achieves O(nk) time and O(k) space.

How to solve Best Time to Buy and Sell Stock IV in O(n)?

O(n) time is possible when k is greater than or equal to n/2. In that scenario the constraint on transactions becomes irrelevant, so the solution simply sums all positive differences between consecutive prices, equivalent to unlimited transactions.

What is the best approach for Best Time to Buy and Sell Stock IV?

The most efficient approach uses dynamic programming with state compression. It tracks buy and sell states for each transaction and updates them while iterating through prices. This solution runs in O(nk) time and O(k) space, which is optimal for the constrained transaction version of the stock trading problem.

Is Best Time to Buy and Sell Stock IV asked at Google/Amazon/Meta?

Variations of the stock trading dynamic programming problems frequently appear in interviews at companies like Amazon, Google, Meta, and Microsoft. Interviewers often extend the problem with constraints such as cooldowns, transaction fees, or limited transactions.

What data structure is used in Best Time to Buy and Sell Stock IV?

The core structure is a dynamic programming state array that tracks profit after each buy or sell operation. Implementations often use arrays like buy[k+1] and sell[k+1] to represent transaction states while iterating through the price array.

What is the time complexity of Best Time to Buy and Sell Stock IV?

The standard dynamic programming solution runs in O(nk) time where n is the number of days and k is the maximum number of transactions. Space complexity is O(k) using state compression or O(nk) with a full DP table.

Best Time to Buy and Sell Stock IV solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with State Compression

Approach 2: State-based Dynamic Programming

Approach 3: Memoization Search

Approach 4: Dynamic Programming

Approach 5: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Best Time to Buy and Sell Stock IV solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with State Compression

Approach 2: State-based Dynamic Programming

Approach 3: Memoization Search

Approach 4: Dynamic Programming

Approach 5: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems