3573. Best Time to Buy and Sell Stock V
Problem Description
You are given an integer array prices where prices[i] is the price of a stock in dollars on the ith day, and an integer k.
You are allowed to make at most k transactions, where each transaction can be either of the following:
- Normal transaction: Buy on day
i, then sell on a later dayjwherei < j. You profitprices[j] - prices[i]. - Short selling transaction: Sell on day
i, then buy back on a later dayjwherei < j. You profitprices[i] - prices[j].
Note that you must complete each transaction before starting another. Additionally, you can't buy or sell on the same day you are selling or buying back as part of a previous transaction.
Return the maximum total profit you can earn by making at most k transactions.
Intuition
To solve this problem, think of each valid action you can take on every day—buying a stock, selling a stock, opening a short position, or closing a short position. With each allowed transaction, you can either buy low and sell high (normal) or sell high and buy low (short selling), but must always finish one before starting a new one.
Because you can only do one action at a time and must alternate between holding nothing, holding a stock (long), or holding a short position, we can track your situation with three separate states. Each day, for each number of transactions left, decide whether to do nothing, continue holding, or transition to a new state by opening or closing a position, always picking whichever option results in the most profit so far.
By using dynamic programming with these states—resting, holding a stock, or holding a short—you can systematically explore all choices, making sure you never overlap transactions or break the rules. The intuition is to keep a running tally for each state and transaction count, always choosing the maximum profit at every step.
Solution Approach
This problem is solved using dynamic programming, keeping track of your possible states as you manage up to k transactions.
We use a 3D DP array:
f[i][j][s]i: The current day (0-based).j: Number of transactions used (from 0 up tok).s: The current state—0means no position,1means holding a stock (long),2means holding a short position.
Initialization:
On day 0, for every possible transaction count (from 1 up to k), you can:
- Buy a stock: set
f[0][j][1] = -prices[0] - Open a short: set
f[0][j][2] = prices[0] - Do nothing:
f[0][j][0] = 0
Transitions:
For every day i (1 to n-1) and transaction count j (1 to k), update the states:
- No stock held:
f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1] + prices[i], f[i-1][j][2] - prices[i])- Either do nothing, sell a stock you held, or buy back a short you held.
- Holding a stock:
f[i][j][1] = max(f[i-1][j][1], f[i-1][j-1][0] - prices[i])- Either keep holding, or start a new long by buying (after resting and with one less transaction left).
- Holding a short:
f[i][j][2] = max(f[i-1][j][2], f[i-1][j-1][0] + prices[i])- Either keep holding your short, or begin a new short (after resting and with one less transaction).
Final Answer:
At the end of all days, the best result is when you are holding no position, after up to k transactions:
Return f[n-1][k][0].
This state design ensures you never overlap transactions, always close one before opening another, and makes full use of both normal and short-selling opportunities for maximum profit.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example step by step to see how the dynamic programming approach works.
Example:
Suppose prices = [3, 2, 5, 1, 4] and k = 2.
There are 5 days, and up to 2 transactions can be made.
Initial State:
On day 0 (first day), for each possible transaction count (j from 1 to 2):
- No position:
f[0][j][0] = 0 - Holding a stock (long):
f[0][j][1] = -prices[0] = -3 - Holding a short:
f[0][j][2] = prices[0] = 3
Day by Day State Updates:
Let's use j = 1, 2 for number of transactions left, and update the DP table:
Day 1 (i = 1, prices[1] = 2):
For j = 1:
-
No position:
f[1][1][0] = max(f[0][1][0], f[0][1][1] + 2, f[0][1][2] - 2)=max(0, -3 + 2, 3 - 2)→max(0, -1, 1)→ 1 -
Holding stock:
f[1][1][1] = max(f[0][1][1], f[0][0][0] - 2)Sincef[0][0][0]doesn’t exist (can’t use 0 transactions to buy), justf[0][1][1] = -3 -
Holding short:
f[1][1][2] = max(f[0][1][2], f[0][0][0] + 2)Again, justf[0][1][2] = 3
For j = 2 (same logic, but can start new positions if previous rest state exists):
- No position:
f[1][2][0] = max(0, -3 + 2, 3 - 2)→1 - Holding stock:
f[1][2][1] = max(-3, 0 - 2)→max(-3, -2)→ -2 - Holding short:
f[1][2][2] = max(3, 0 + 2)→3
Day 2 (i = 2, prices[2] = 5):
For j = 1:
- No position:
f[2][1][0] = max(1, -3 + 5, 3 - 5)→max(1, 2, -2)→ 2 - Holding stock:
f[2][1][1] = max(-3, (doesn't exist))→ -3 - Holding short:
f[2][1][2] = max(3, (doesn't exist))→ 3
For j = 2:
- No position:
f[2][2][0] = max(1, -2 + 5, 3 - 5)→max(1, 3, -2)→ 3 - Holding stock:
f[2][2][1] = max(-2, 1 - 5)→max(-2, -4)→ -2 - Holding short:
f[2][2][2] = max(3, 1 + 5)→max(3, 6)→ 6
Day 3 (i = 3, prices[3] = 1):
For j = 1:
- No position:
f[3][1][0] = max(2, -3 + 1, 3 - 1)→max(2, -2, 2)→ 2 - Holding stock:
f[3][1][1] = max(-3, (doesn't exist))→ -3 - Holding short:
f[3][1][2] = max(3, (doesn't exist))→ 3
For j = 2:
- No position:
f[3][2][0] = max(3, -2 + 1, 6 - 1)→max(3, -1, 5)→ 5 - Holding stock:
f[3][2][1] = max(-2, 3 - 1)→max(-2, 2)→ 2 - Holding short:
f[3][2][2] = max(6, 3 + 1)→6
Day 4 (i = 4, prices[4] = 4):
For j = 1:
- No position:
f[4][1][0] = max(2, -3 + 4, 3 - 4)→max(2, 1, -1)→ 2 - Holding stock:
f[4][1][1] = max(-3, (doesn't exist))→ -3 - Holding short:
f[4][1][2] = max(3, (doesn't exist))→ 3
For j = 2:
- No position:
f[4][2][0] = max(5, 2 + 4, 6 - 4)→max(5, 6, 2)→ 6 - Holding stock:
f[4][2][1] = max(2, 5 - 4)→max(2, 1)→ 2 - Holding short:
f[4][2][2] = max(6, 5 + 4)→max(6, 9)→ 9
Final Answer:
After the last day (i = 4), with at most 2 transactions, the maximum profit when holding no position is:
f[4][2][0] = 6
Interpretation:
The optimal sequence could involve, for example, opening a short at day 0 (sell at 3), closing at day 1 (buy at 2, profit 1), then buying at day 3 (at 1), and selling at day 4 (at 4, profit 3), for total profit 1 + 3 = 4, but with the DP, the global maximum including all state transitions is captured as 6, possibly by other combinations (such as using the short/long in different orders).
This walk-through illustrates how the three-state DP systematically evaluates all possibilities and computes the answer.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maximumProfit(self, prices: List[int], k: int) -> int:
5 n = len(prices)
6 # DP table: dp[day][transactions][state]
7 # state: 0 = no stock, 1 = holding stock (buy), 2 = holding short (sell first)
8 dp = [[[0] * 3 for _ in range(k + 1)] for _ in range(n)]
9
10 # Initialization for day 0
11 for transactions in range(1, k + 1):
12 dp[0][transactions][1] = -prices[0] # Buy stock on day 0
13 dp[0][transactions][2] = prices[0] # Short sell stock on day 0
14
15 # Fill the DP table
16 for day in range(1, n):
17 for transactions in range(1, k + 1):
18 # State 0: Currently not holding any position
19 dp[day][transactions][0] = max(
20 dp[day - 1][transactions][0], # Do nothing
21 dp[day - 1][transactions][1] + prices[day], # Sell held stock
22 dp[day - 1][transactions][2] - prices[day] # Cover short position
23 )
24 # State 1: Currently holding stock (after buy)
25 dp[day][transactions][1] = max(
26 dp[day - 1][transactions][1], # Hold stock
27 dp[day - 1][transactions - 1][0] - prices[day] # Buy stock
28 )
29 # State 2: Currently holding short position (after sell first)
30 dp[day][transactions][2] = max(
31 dp[day - 1][transactions][2], # Hold short
32 dp[day - 1][transactions - 1][0] + prices[day] # Short sell
33 )
34 # The answer is the maximum profit at the last day with no position
35 return dp[n - 1][k][0]
361class Solution {
2 public long maximumProfit(int[] prices, int k) {
3 int n = prices.length;
4 // dp[i][j][state]: Max profit at day i, with j transactions, and in 'state'
5 // state: 0 = not holding, 1 = holding (after buying), 2 = short-selling (after selling first)
6 long[][][] dp = new long[n][k + 1][3];
7
8 // Initialization for day 0
9 for (int j = 1; j <= k; ++j) {
10 dp[0][j][1] = -prices[0]; // Buy on day 0
11 dp[0][j][2] = prices[0]; // Short-sell on day 0
12 }
13
14 // State transition for each day
15 for (int day = 1; day < n; ++day) {
16 for (int transaction = 1; transaction <= k; ++transaction) {
17 // State 0: Not holding anything
18 // Max of:
19 // - rest from previous day (dp[day-1][transaction][0])
20 // - sell today if we were holding a stock (dp[day-1][transaction][1] + prices[day])
21 // - cover a short position today (dp[day-1][transaction][2] - prices[day])
22 dp[day][transaction][0] = Math.max(
23 dp[day - 1][transaction][0],
24 Math.max(
25 dp[day - 1][transaction][1] + prices[day], // Sell held stock
26 dp[day - 1][transaction][2] - prices[day] // Cover short
27 )
28 );
29
30 // State 1: Holding a stock after buying (haven't sold yet)
31 // Max of:
32 // - keep holding from previous day
33 // - buy today (have to be in state 0 yesterday and do a new transaction)
34 dp[day][transaction][1] = Math.max(
35 dp[day - 1][transaction][1],
36 dp[day - 1][transaction - 1][0] - prices[day]
37 );
38
39 // State 2: In a short-sell (after selling without owning)
40 // Max of:
41 // - keep short from previous day
42 // - start a new short today (must have been in state 0 yesterday and it's a new transaction)
43 dp[day][transaction][2] = Math.max(
44 dp[day - 1][transaction][2],
45 dp[day - 1][transaction - 1][0] + prices[day]
46 );
47 }
48 }
49
50 // The answer is the maximum profit with at most k transactions, at last day, and not holding any position
51 return dp[n - 1][k][0];
52 }
53}
541class Solution {
2public:
3 // Calculates the maximum profit from at most k stock transactions
4 long long maximumProfit(vector<int>& prices, int k) {
5 int n = prices.size();
6 // Dynamic programming table:
7 // dp[day][transaction_count][state]
8 // state: 0 = hold nothing, 1 = holding stock, 2 = holding short
9 long long dp[n][k + 1][3];
10 memset(dp, 0, sizeof(dp));
11
12 // Initialize state for day 0
13 for (int trans = 1; trans <= k; ++trans) {
14 dp[0][trans][1] = -prices[0]; // Bought a stock
15 dp[0][trans][2] = prices[0]; // Sold short (equivalent to holding a short position)
16 }
17
18 // Fill DP table
19 for (int day = 1; day < n; ++day) {
20 for (int trans = 1; trans <= k; ++trans) {
21 // Not holding any position: do nothing OR sell stock OR cover short
22 dp[day][trans][0] = max({
23 dp[day - 1][trans][0], // Do nothing
24 dp[day - 1][trans][1] + prices[day], // Sell stock held
25 dp[day - 1][trans][2] - prices[day] // Cover short position
26 });
27 // Holding a stock: do nothing OR buy today (used another transaction)
28 dp[day][trans][1] = max(
29 dp[day - 1][trans][1], // Hold stock
30 dp[day - 1][trans - 1][0] - prices[day] // Buy stock using up a transaction
31 );
32 // Holding a short: do nothing OR short today (used another transaction)
33 dp[day][trans][2] = max(
34 dp[day - 1][trans][2], // Hold short
35 dp[day - 1][trans - 1][0] + prices[day] // Start short position using up a transaction
36 );
37 }
38 }
39
40 // Maximum profit ends up with no stock or short held (state = 0)
41 return dp[n - 1][k][0];
42 }
43};
441/**
2 * Calculates the maximum profit from at most k transactions,
3 * with buy and sell allowed (and separately, short-sell and cover).
4 *
5 * @param prices - Array of stock prices.
6 * @param k - Maximum number of transactions allowed.
7 * @returns The maximum profit possible.
8 */
9function maximumProfit(prices: number[], k: number): number {
10 const n = prices.length;
11 // 3D DP array:
12 // dp[day][transactions][state]
13 // state: 0 = not holding, 1 = holding (long), 2 = holding short
14 const dp: number[][][] = Array.from({ length: n }, () =>
15 Array.from({ length: k + 1 }, () => Array(3).fill(0)),
16 );
17
18 // Initialize DP for the first day for each number of transactions
19 for (let transactions = 1; transactions <= k; ++transactions) {
20 dp[0][transactions][1] = -prices[0]; // Buy (long) on the first day
21 dp[0][transactions][2] = prices[0]; // Short-sell on the first day
22 }
23
24 // Iterate over days
25 for (let day = 1; day < n; ++day) {
26 // Iterate over possible transaction counts
27 for (let transactions = 1; transactions <= k; ++transactions) {
28 // 0: Not holding any stock
29 dp[day][transactions][0] = Math.max(
30 dp[day - 1][transactions][0], // Do nothing
31 dp[day - 1][transactions][1] + prices[day], // Sell (close long)
32 dp[day - 1][transactions][2] - prices[day], // Cover (close short)
33 );
34 // 1: Holding stock (long position)
35 dp[day][transactions][1] = Math.max(
36 dp[day - 1][transactions][1], // Do nothing, keep holding
37 dp[day - 1][transactions - 1][0] - prices[day], // Buy new stock
38 );
39 // 2: Holding short position
40 dp[day][transactions][2] = Math.max(
41 dp[day - 1][transactions][2], // Do nothing, keep holding
42 dp[day - 1][transactions - 1][0] + prices[day], // Short-sell new stock
43 );
44 }
45 }
46
47 // Final result: finish trading with no position on the last day, after at most k transactions
48 return dp[n - 1][k][0];
49}
50Time and Space Complexity
The time complexity of the code is O(n * k), where n is the length of the prices array and k is the maximum number of transactions. This is because the three nested loops iterate over n days, k transactions, and a constant number of states.
The space complexity is also O(n * k), as the 3D DP array f has dimensions [n][k+1][3], which is dominated by n * k.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!