Best Time to Buy and Sell Stock IV: At Most K Transactions

50.8k
0

Given an integer k and an array prices, prices[day] stores the stock price on a particular day. At most k transactions may be completed.

One transaction contains one buy followed by one sell. A second stock cannot be bought before the current stock has been sold. Return the maximum possible profit, with zero profit allowed.

Example 1

Input: k = 2, prices = [5, 2, 4, 0, 3, 7]
Output: 9
Explanation: Buying at 2 and selling at 4 earns 2. Buying at 0 and selling at 7 earns 7, producing total profit 9.

Example 2

Input: k = 3, prices = [8, 6, 4, 2]
Output: 0
Explanation: Every later price is smaller, so skipping all transactions preserves profit 0.

Recursion

Each day presents a choice based on the current trading state. When buying is allowed, we can either buy the stock at the current price or skip the day. When already holding a stock, we can either sell it or continue holding. Exploring both choices allows us to find the maximum profit while respecting the transaction limit.

The state solve(day, canBuy, remainingTransactions) stores the maximum profit possible from that decision point onward. The initial call is solve(0, 1, k) because trading starts before Day 0, with no stock held, buying allowed, and all k transactions available.

Algorithm

  • Start with solve(0, 1, k) because trading begins before the first day with buying allowed and the full transaction limit available.

  • Stop when day reaches the end of the array or remainingTransactions becomes 0, because no further profitable transaction can be completed.

  • In the buying state, compare buying for -prices[day] with skipping the day, because either choice may lead to the maximum profit.

  • Keep remainingTransactions unchanged after buying because a transaction is completed only when the stock is sold.

  • In the selling state, compare selling for prices[day] with continuing to hold the stock, because either choice may produce the better profit.

  • Decrease remainingTransactions after selling because the sale completes one buy-sell transaction.

  • Return the larger value from the two choices at each state because we want the maximum valid profit.

Dry Run

Diagram 1
1 / 3

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds the best profit from one trading state.
int solve(
int day,
int canBuy,
int remainingTransactions,
vector<int>& prices
) {
int n = prices.size();
// No completed sale remains beyond either limit.
if (day == n || remainingTransactions == 0) {
return 0;
}
// A free state can buy or wait.
if (canBuy == 1) {
// Buying keeps the sale capacity unchanged.
int buyProfit = -prices[day] + solve(
day + 1,
0,
remainingTransactions,
prices
);
// Skipping preserves the free state.
int skipProfit = solve(
day + 1,
1,
remainingTransactions,
prices
);
// The larger branch gives the best free-state profit.
return max(buyProfit, skipProfit);
}
// Selling closes one complete transaction.
int sellProfit = prices[day] + solve(
day + 1,
1,
remainingTransactions - 1,
prices
);
// Holding preserves the current stock and capacity.
int holdProfit = solve(
day + 1,
0,
remainingTransactions,
prices
);
// The larger branch gives the best holding-state profit.
return max(sellProfit, holdProfit);
}
public:
// Finds the maximum profit with at most k transactions.
int maxProfit(int k, vector<int>& prices) {
// Trading starts free to buy with full capacity.
return solve(0, 1, k, prices);
}
};
// Driver code
int main() {
int k = 2;
vector<int> prices = {5, 2, 4, 0, 3, 7};
Solution obj;
cout << obj.maxProfit(k, prices);
return 0;
}

Complexity Analysis

Time Complexity: O(2N), where N is the number of days, because each day can create two recursive choices across a recursion depth of at most N.

Space Complexity: O(N), because one active recursion path contains at most one call for each day.

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Memoization

Many recursive paths can reach the same combination of day, buying state, and remaining transactions. Without memoization, the same future choices are recalculated repeatedly, wasting recursive work.

A three-dimensional dp array stores the maximum profit for each reachable state. The recursive decisions remain unchanged, but a previously calculated state can return its saved answer immediately instead of exploring the same recursive tree again.

Algorithm

  • Begin with solve(0, 1, k) because memoization preserves the same recursive state and transaction rules.

  • Create dp[day][canBuy][remainingTransactions] with -1 entries, so every uncomputed state is distinguishable from a valid profit of 0.

  • Stop when day reaches the end of the array or remainingTransactions becomes 0, because no further completed transaction is possible.

  • Return the existing dp value before exploring branches, so repeated states avoid duplicate recursive work.

  • In a buying state, compare buying with skipping while keeping the remaining transaction count unchanged after a purchase.

  • In a selling state, compare selling with holding and decrease the remaining count after a sale, because one completed buy-sell pair consumes one transaction.

  • Store the larger branch value in dp and return it, so future visits receive the best profit already calculated for that state.

Dry Run

Diagram 1
1 / 3

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds and stores the best profit from one state.
int solve(
int day,
int canBuy,
int remainingTransactions,
vector<int>& prices,
vector<vector<vector<int>>>& dp
) {
int n = prices.size();
// No completed sale remains beyond either limit.
if (day == n || remainingTransactions == 0) {
return 0;
}
// A stored state avoids repeated branch exploration.
if (dp[day][canBuy][remainingTransactions] != -1) {
return dp[day][canBuy][remainingTransactions];
}
// A free state can buy or wait.
if (canBuy == 1) {
// Buying keeps the sale capacity unchanged.
int buyProfit = -prices[day] + solve(
day + 1,
0,
remainingTransactions,
prices,
dp
);
// Skipping preserves the free state.
int skipProfit = solve(
day + 1,
1,
remainingTransactions,
prices,
dp
);
// Cache the best free-state branch for reuse.
dp[day][canBuy][remainingTransactions] = max(
buyProfit,
skipProfit
);
return dp[day][canBuy][remainingTransactions];
}
// Selling closes one complete transaction.
int sellProfit = prices[day] + solve(
day + 1,
1,
remainingTransactions - 1,
prices,
dp
);
// Holding preserves the current stock and capacity.
int holdProfit = solve(
day + 1,
0,
remainingTransactions,
prices,
dp
);
// Cache the best holding-state branch for reuse.
dp[day][canBuy][remainingTransactions] = max(
sellProfit,
holdProfit
);
return dp[day][canBuy][remainingTransactions];
}
public:
// Finds the maximum profit with at most k transactions.
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
// A negative entry marks an uncalculated state.
vector<vector<vector<int>>> dp(
n,
vector<vector<int>>(
2,
vector<int>(k + 1, -1)
)
);
// Trading starts free to buy with full capacity.
return solve(0, 1, k, prices, dp);
}
};
// Driver code
int main() {
int k = 2;
vector<int> prices = {5, 2, 4, 0, 3, 7};
Solution obj;
cout << obj.maxProfit(k, prices);
return 0;
}

Complexity Analysis

Time Complexity: O(N × K), where N is the number of days and K is the maximum number of transactions, because at most N × 2 × K trading states are evaluated once with constant transition work.

Space Complexity: O(N × K + N), because the dp table stores every trading state, while the recursion stack can contain up to N calls.

Tabulation

Memoization still depends on recursive calls. A bottom-up table can evaluate the same states directly, beginning with the known zero-profit states after the final day.

Every state reads values from the next day, so reverse day order makes all required answers available. The table keeps the same buying flag and remaining transaction count from recursion.

Algorithm

  • Build dp with n + 1 day layers, two buying states, and k + 1 transaction counts so every recursive state has a matching table cell.

  • Keep the extra final-day layer and every zero-transaction cell at 0 because no completed sale can follow either base state.

  • Traverse days from n - 1 down to 0 because each current transition depends only on already calculated next-day values.

  • Process remaining transaction counts from 1 through k because count 0 must preserve the stopping value.

  • Fill the buying cell from buy and skip choices so the better entry decision is saved without consuming a transaction.

  • Fill the selling cell from sell and hold choices so only a completed sale reads the smaller remaining count.

  • Return dp[0][1][k] because the first day, free buying state, and full capacity represent the complete problem.

Dry Run

Best Time to Buy and Sell Stock IV Tabulation

Best Time to Buy and Sell Stock IV Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the maximum profit with bottom-up states.
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
// Zero values cover both stopping conditions.
vector<vector<vector<int>>> dp(
n + 1,
vector<vector<int>>(
2,
vector<int>(k + 1, 0)
)
);
// Reverse order prepares every required next-day state.
for (int day = n - 1; day >= 0; day--) {
// Positive counts allow a complete sale.
for (
int remainingTransactions = 1;
remainingTransactions <= k;
remainingTransactions++
) {
// Buying compares an entry with a skipped day.
int buyProfit = -prices[day]
+ dp[day + 1][0][remainingTransactions];
int skipProfit =
dp[day + 1][1][remainingTransactions];
dp[day][1][remainingTransactions] = max(
buyProfit,
skipProfit
);
// Selling closes one complete transaction.
int sellProfit = prices[day]
+ dp[day + 1][1][remainingTransactions - 1];
int holdProfit =
dp[day + 1][0][remainingTransactions];
dp[day][0][remainingTransactions] = max(
sellProfit,
holdProfit
);
}
}
// The starting state contains the complete answer.
return dp[0][1][k];
}
};
// Driver code
int main() {
int k = 2;
vector<int> prices = {5, 2, 4, 0, 3, 7};
Solution obj;
cout << obj.maxProfit(k, prices);
return 0;
}

Complexity Analysis

Time Complexity: O(N × K), where N is the number of days and K is the maximum number of transactions, because the reverse traversal evaluates N × 2 × K states with constant work per state.

Space Complexity: O(N × K), because the three-dimensional dp table stores two buying states for every day and transaction count, and no recursion stack is used.

Space Optimization

Each tabulation layer reads only the next day. Older day layers never appear in a current transition, so the full day dimension carries unnecessary history.

Two small layers are enough. ahead stores the next-day answers, while current receives both choices for the active day. After all transaction counts are finished, current becomes the new ahead layer.

Algorithm

  • Create ahead and current with two buying states and k + 1 transaction counts because one day transition needs only the next-day layer.

  • Leave count 0 at 0 in both layers because no completed sale remains after all transaction capacity is used.

  • Traverse days from right to left so ahead always represents every next-day state required by the active day.

  • Recreate current for each day so values from an older day cannot leak into the active layer.

  • Calculate buying-state values from ahead by comparing a purchase against a skip without reducing the transaction count.

  • Calculate selling-state values from ahead by comparing a sale against a hold and reducing the count only for the sale.

  • Shift current into ahead only after the full day is complete so every active transition reads a fully calculated future layer.

  • Return ahead[1][k] after day 0 becomes the saved layer because the starting state represents the complete trading problem.

Dry Run

best-time-to-buy-and-sell-stock-iv-space-optimization

best-time-to-buy-and-sell-stock-iv-space-optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the maximum profit with rolling state layers.
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
// The saved layer begins at the final-day base state.
vector<vector<int>> ahead(
2,
vector<int>(k + 1, 0)
);
// Reverse order keeps the next day available.
for (int day = n - 1; day >= 0; day--) {
// A fresh layer prevents stale current-day values.
vector<vector<int>> current(
2,
vector<int>(k + 1, 0)
);
// Positive counts allow a complete sale.
for (
int remainingTransactions = 1;
remainingTransactions <= k;
remainingTransactions++
) {
// Current buy values use the next-day layer.
int buyProfit = -prices[day]
+ ahead[0][remainingTransactions];
int skipProfit = ahead[1][remainingTransactions];
current[1][remainingTransactions] = max(
buyProfit,
skipProfit
);
// Current sell values use the next-day layer.
int sellProfit = prices[day]
+ ahead[1][remainingTransactions - 1];
int holdProfit = ahead[0][remainingTransactions];
current[0][remainingTransactions] = max(
sellProfit,
holdProfit
);
}
// Shift current after every count is complete.
ahead = current;
}
// The saved starting state contains the final answer.
return ahead[1][k];
}
};
// Driver code
int main() {
int k = 2;
vector<int> prices = {5, 2, 4, 0, 3, 7};
Solution obj;
cout << obj.maxProfit(k, prices);
return 0;
}

Complexity Analysis

Time Complexity: O(N × K), where N is the number of days and K is the maximum number of transactions, because each day evaluates both trading states for every transaction count with constant work.

Space Complexity: O(K), because the ahead and current arrays each store two values for every transaction count, and no older day layer is retained.

Interview follow-up Questions

Yes. The limit allows at most k transactions, so every unprofitable trade can be skipped.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or second % first == 0...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a t...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals target ; otherwise,...

55.1k
Comments0