Log inSign up
hardLeetCodeNot Started

Best Time to Buy and Sell Stock IV

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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. Total profit is 4 + 3 = 7.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Recognize when constraints relax into greedy sub-problems (k >= n / 2).
  • Generalize 2-transaction state machines to arbitrary K transactions.
  • Achieve O(n \cdot k) time and O(k) space complexity.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Stock price array with explicit parameter k denoting maximum transaction count.
  • Constraints allow k up to 100 and n up to 1000.

Algorithmic Decision Tree:

  • Check if k >= n/2: bypass DP with greedy O(n) slope accumulation.
  • Otherwise: run DP with k states.

Connected Patterns:

Best Time to Buy and Sell Stock III0/1 Knapsack (bounded resource DP)

1. Recursive DFS with Memoization

Intuition

Explore recursive states (day, transactions_remaining, holding). At each step, either buy, sell, or skip.

Algorithm

  1. Define dfs(day, k, holding).
  2. Base Case: If day == n or k == 0, return 0.
  3. If holding: choice 1 is sell prices[day] + dfs(day + 1, k - 1, 0); choice 2 is keep dfs(day + 1, k, 1).
  4. If not holding: choice 1 is buy -prices[day] + dfs(day + 1, k, 1); choice 2 is skip dfs(day + 1, k, 0).
  5. Return max of options.

Recursive Transaction Count Search

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
First optimal trade
Visual state
Values and pointers at this exact step
table
S
buy@2 -> sell@6
0
t1Profit4
remainingK1
Variables at this step
t1Profit
4
remainingK
1
Check / comparison
First transaction: buy at 2, sell at 6 -> gain = 6 - 2 = 4
Decision / next transition
Gain = 4, 1 transaction remaining.
Why this step matters

First optimal trade.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <cstring>
5
6using namespace std;
7
8int memo[1005][105][2];
9
10int dfs(int day, int k, int holding, const vector<int>& prices) {
11 if (day == (int)prices.size() || k == 0) return 0;
12 if (memo[day][k][holding] != -1) return memo[day][k][holding];
13
14 if (holding) {
15 int sell = prices[day] + dfs(day + 1, k - 1, 0, prices);
16 int keep = dfs(day + 1, k, 1, prices);
17 return memo[day][k][holding] = max(sell, keep);
18 } else {
19 int buy = -prices[day] + dfs(day + 1, k, 1, prices);
20 int skip = dfs(day + 1, k, 0, prices);
21 return memo[day][k][holding] = max(buy, skip);
22 }
23}
24
25int maxProfitMemo(int k, const vector<int>& prices) {
26 if (prices.empty() || k == 0) return 0;
27 memset(memo, -1, sizeof(memo));
28 return dfs(0, k, 0, prices);
29}
30
31int main() {
32 vector<int> prices = {3, 2, 6, 5, 0, 3};
33 int k = 2;
34 cout << "Max Profit (Memoized DFS): " << maxProfitMemo(k, prices) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(2^n) without memo, O(n * k) with full 3D memo table
  • Space complexity: O(n * k) memoization table and call stack

2. 2D Tabulation DP (Transactions x Days)

Intuition

Build table dp[t][i] storing the max profit with at most t transactions up to day i.

Algorithm

  1. If k >= n / 2, return greedy sum of positive differences.
  2. Initialize dp[k + 1][n] to 0.
  3. For t = 1 to k:
  4. maxDiff = -prices[0]
  5. For i = 1 to n - 1:
  6. dp[t][i] = max(dp[t][i - 1], prices[i] + maxDiff)
  7. maxDiff = max(maxDiff, dp[t - 1][i] - prices[i])
  8. Return dp[k][n - 1].

2D Dynamic Programming (dp[t][i])

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
t=1 matches LeetCode 121 (single transaction)
Visual state
Values and pointers at this exact step
table
S
max=4
0
t1
maxProfit14
Variables at this step
t
1
maxProfit1
4
Check / comparison
Transaction 1 DP row: max profit with 1 trade
Decision / next transition
Best 1-trade profit is buy at 2, sell at 6 -> profit = 4.
Why this step matters

t=1 matches LeetCode 121 (single transaction).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maxProfit2D(int k, const vector<int>& prices) {
8 int n = prices.size();
9 if (n <= 1 || k == 0) return 0;
10
11 if (k >= n / 2) {
12 int profit = 0;
13 for (int i = 1; i < n; i++) {
14 if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
15 }
16 return profit;
17 }
18
19 vector<vector<int>> dp(k + 1, vector<int>(n, 0));
20 for (int t = 1; t <= k; t++) {
21 int maxDiff = -prices[0];
22 for (int i = 1; i < n; i++) {
23 dp[t][i] = max(dp[t][i - 1], prices[i] + maxDiff);
24 maxDiff = max(maxDiff, dp[t - 1][i] - prices[i]);
25 }
26 }
27 return dp[k][n - 1];
28}
29
30int main() {
31 vector<int> prices = {3, 2, 6, 5, 0, 3};
32 int k = 2;
33 cout << "Max Profit (2D Tabulation): " << maxProfit2D(k, prices) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(k * n)
  • Space complexity: O(k * n)

3. 1D Rolling Arrays O(k) Space DP

Intuition

Maintain two arrays buy[k + 1] and sell[k + 1] representing the max balance after buying/selling on transaction t.

Algorithm

  1. If k >= n / 2, return greedy sum of positive price steps.
  2. Initialize buy array of size k + 1 filled with -prices[0] (or -INF).
  3. Initialize sell array of size k + 1 filled with 0.
  4. For each price in prices:
  5. For t = 1 to k:
  6. buy[t] = max(buy[t], sell[t - 1] - price)
  7. sell[t] = max(sell[t], buy[t] + price)
  8. Return sell[k].

1D Array State Machine (buy[k] & sell[k])

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Tracks balances for 1st and 2nd transactions
Visual state
Values and pointers at this exact step
table
S
buy:[-3,-3], sell:[0,0]
0
buy[-3,-3]
sell[0,0]
Variables at this step
buy
[-3,-3]
sell
[0,0]
Check / comparison
Initialize: buy = [-3, -3], sell = [0, 0] for k=2
Decision / next transition
State machine array initialized.
Why this step matters

Tracks balances for 1st and 2nd transactions.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maxProfitOptimal(int k, const vector<int>& prices) {
8 int n = prices.size();
9 if (n <= 1 || k == 0) return 0;
10
11 if (k >= n / 2) {
12 int profit = 0;
13 for (int i = 1; i < n; i++) {
14 if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
15 }
16 return profit;
17 }
18
19 vector<int> buy(k + 1, -prices[0]);
20 vector<int> sell(k + 1, 0);
21
22 for (int p : prices) {
23 for (int t = 1; t <= k; t++) {
24 buy[t] = max(buy[t], sell[t - 1] - p);
25 sell[t] = max(sell[t], buy[t] + p);
26 }
27 }
28 return sell[k];
29}
30
31int main() {
32 vector<int> prices = {3, 2, 6, 5, 0, 3};
33 int k = 2;
34 cout << "Max Profit (Optimal O(k) Space): " << maxProfitOptimal(k, prices) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(n * k)
  • Space complexity: O(k) space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Memoized DFSO(n * k)O(n * k)Top-down recursion over (day, k, holding).Table allocation and call stack
2.2D TabulationO(n * k)O(n * k)Table dp[t][i] tracking maxDiff = dp[t-1][j] - prices[j].2D table memory
3.Rolling 1D ArraysOptimalO(n * k)O(k)Maintain buy[k+1] and sell[k+1] rolling arrays with greedy k >= n/2 shortcut.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Allocating an array of size k + 1 when k is very large (e.g. k = 109) without the k >= n / 2 check, causing OutOfMemoryError.

Pitfall 2:

Initializing buy array to 0 instead of -prices[0] or -infinity.

Crucial Edge Cases to Validate:

  • k = 0 or prices is empty: Profit is 0.
  • k >= n / 2: Handled by greedy check, preventing large array allocations.
  • Strictly falling prices: Output is 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the edge case where k >= n / 2 immediately! Interviewers love seeing candidates catch this optimization before allocating DP tables.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can we switch directly to a greedy O(n) algorithm when k >= n / 2?

Back to DSA Sheet