Facebook Pixel

3573. Best Time to Buy and Sell Stock V

MediumArrayDynamic Programming
Leetcode Link

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 day j where i < j. You profit prices[j] - prices[i].
  • Short selling transaction: Sell on day i, then buy back on a later day j where i < j. You profit prices[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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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 to k).
    • s: The current state—0 means no position, 1 means holding a stock (long), 2 means 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 Evaluator

Example 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) Since f[0][0][0] doesn’t exist (can’t use 0 transactions to buy), just f[0][1][1] = -3

  • Holding short: f[1][1][2] = max(f[0][1][2], f[0][0][0] + 2) Again, just f[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]
36
1class 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}
54
1class 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};
44
1/**
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}
50

Time 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Dynamic Programming Introduction and Patterns

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: The Smart, Data-Driven Way to Prepare for Tech Interviews

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 Review

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!

Load More