# Best Time to Buy and Sell Stock IV
**Difficulty:** HARD
[External](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv)
Canonical: https://scaleengineer.com/dsa/problems/best-time-to-buy-and-sell-stock-iv
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Nielsen](https://scaleengineer.com/companies/nielsen), [Nvidia](https://scaleengineer.com/companies/nvidia), [Citadel](https://scaleengineer.com/companies/citadel), [PhonePe](https://scaleengineer.com/companies/phonepe), [Arcesium](https://scaleengineer.com/companies/arcesium), [Jump Trading](https://scaleengineer.com/companies/jump-trading)
---
## Problem
You are given an integer array `prices` where `prices[i]` is the price of a given stock on the `ith` 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`

# Approaches
## Brute-Force Recursion
This approach attempts to solve the problem by exploring every possible sequence of transactions. It uses a recursive function that, for each day, decides between the possible actions: buy, sell, or do nothing. This generates a decision tree of all possibilities, and the path with the maximum profit is chosen.
**Time:** O(2^n) · **Space:** O(n)
**Pros:** Conceptually straightforward and follows the problem statement directly.
**Cons:** Extremely inefficient due to exponential time complexity.; Results in 'Time Limit Exceeded' for even moderately sized inputs.; Redundantly computes the same subproblems multiple times.
### Explanation
The core of this method is a recursive function, let's call it `solve(day, transactions_completed, holding)`. This function calculates the maximum profit achievable from a given `day` onwards, given that we have already completed `transactions_completed` and our `holding` status (whether we own a stock or not).

- **State**: The state is defined by `(day, transactions_completed, holding)`.
- **Transitions**:
  - If we are `holding` a stock, we can either sell it today (which increments `transactions_completed`) or hold it and move to the next day.
  - If we are not `holding` a stock, we can either buy one today (which changes our `holding` status) or skip today and move on.
- **Base Cases**: The recursion stops when we have exhausted the days (`day >= prices.length`) or completed the maximum allowed transactions (`transactions_completed >= k`). In these scenarios, no further profit can be made, so we return 0.

The final answer is the result of the initial call `solve(0, 0, false)`.

```java
class Solution {
    public int maxProfit(int k, int[] prices) {
        return solve(0, 0, 0, k, prices);
    }

    private int solve(int day, int transactions, int holding, int k, int[] prices) {
        // Base case: no more days to trade or max transactions reached
        if (day >= prices.length || transactions >= k) {
            return 0;
        }

        // Recursive step
        // Option 1: Do nothing today (rest)
        int restProfit = solve(day + 1, transactions, holding, k, prices);

        int actionProfit;
        if (holding == 1) {
            // Option 2: Sell the stock
            actionProfit = prices[day] + solve(day + 1, transactions + 1, 0, k, prices);
        } else { // holding == 0
            // Option 3: Buy the stock
            actionProfit = -prices[day] + solve(day + 1, transactions, 1, k, prices);
        }
        
        return Math.max(restProfit, actionProfit);
    }
}
```
### Algorithm
1. Define a recursive function `solve(index, k, isHolding)`.
2. Base Case: If `index >= prices.length` or we cannot make any more transactions, return 0.
3. If `isHolding` is true (we have a stock):
    - Calculate profit from selling today: `prices[index] + solve(index + 1, k - 1, false)`.
    - Calculate profit from holding: `solve(index + 1, k, true)`.
    - Return the maximum of these two options.
4. If `isHolding` is false (we don't have a stock):
    - Calculate profit from buying today: `-prices[index] + solve(index + 1, k, true)`.
    - Calculate profit from skipping today: `solve(index + 1, k, false)`.
    - Return the maximum of these two options.
5. The initial call to the function would be `solve(0, k, false)`.

## Recursion with Memoization
This approach enhances the brute-force recursion by using memoization to avoid recomputing results for the same subproblems. We store the result for each state `(day, transactions, holding)` in a cache (a 3D array). When the recursive function is called for a state that has been solved before, we simply return the cached result, pruning the recursion tree significantly. This is a top-down dynamic programming approach.
**Time:** O(n * k) · **Space:** O(n * k)
**Pros:** Guaranteed to find the optimal solution.; Drastically more efficient than brute-force, making it feasible for the given constraints.; Maintains the intuitive recursive structure.
**Cons:** Requires O(n * k) space for the memoization table, which can be large.; May lead to a stack overflow for very deep recursion, although the problem constraints make this unlikely.
### Explanation
We keep the same recursive structure but add a 3D array, `memo[n][k+1][2]`, to store the results of subproblems. `memo[day][transactions][holding]` will store the maximum profit for the state defined by the indices.

Before computing the profit for a state, we first check our `memo` table. If a valid result (i.e., not our initial placeholder value) exists, we return it immediately. Otherwise, we compute the result using the same recursive logic as the brute-force method, and crucially, we store this new result in the `memo` table before returning. This ensures that each unique subproblem is solved only once.

```java
class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        int[][][] memo = new int[n][k + 1][2];
        for (int[][] dayMemo : memo) {
            for (int[] transMemo : dayMemo) {
                Arrays.fill(transMemo, -1);
            }
        }
        return solve(0, 0, 0, k, prices, memo);
    }

    private int solve(int day, int transactions, int holding, int k, int[] prices, int[][][] memo) {
        if (day >= prices.length || transactions >= k) {
            return 0;
        }
        if (memo[day][transactions][holding] != -1) {
            return memo[day][transactions][holding];
        }

        int restProfit = solve(day + 1, transactions, holding, k, prices, memo);

        int actionProfit;
        if (holding == 1) {
            actionProfit = prices[day] + solve(day + 1, transactions + 1, 0, k, prices, memo);
        } else { // holding == 0
            actionProfit = -prices[day] + solve(day + 1, transactions, 1, k, prices, memo);
        }
        
        memo[day][transactions][holding] = Math.max(restProfit, actionProfit);
        return memo[day][transactions][holding];
    }
}
```
### Algorithm
1. Create a 3D memoization table `memo[n][k+1][2]` and initialize it with a value indicating 'not computed' (e.g., -1).
2. Use the same recursive function `solve(day, transactions, holding)` as in the brute-force approach.
3. Before any computation, check if `memo[day][transactions][holding]` has already been computed. If so, return the stored value.
4. If not, perform the recursive calculations as before.
5. After computing the result for a state, store it in `memo[day][transactions][holding]` before returning it.
6. The initial call remains `solve(0, 0, 0, k, prices, memo)`.

## Space-Optimized Bottom-Up Dynamic Programming
This is the most efficient approach, utilizing bottom-up dynamic programming with space optimization. We observe that the calculation for the current day `i` only depends on the results from the previous day `i-1`. This allows us to reduce the space complexity from O(n*k) to O(k). We maintain two arrays, `buy` and `sell`, of size `k+1`, representing the maximum profit at each transaction count, ending in a 'holding' or 'not holding' state, respectively.
**Time:** O(n * k) · **Space:** O(k)
**Pros:** Optimal time complexity of O(n * k).; Optimal space complexity of O(k).; Iterative approach avoids recursion overhead and potential stack overflow issues.
**Cons:** The logic can be less intuitive to derive compared to the recursive top-down approach.
### Explanation
Instead of a large 2D or 3D DP table, we only need to keep track of the profits for the previous day to calculate the profits for the current day. We can achieve this with two 1D arrays:
- `sell[j]`: The maximum profit after completing `j` transactions, ending in a state where we are not holding any stock.
- `buy[j]`: The maximum profit after `j` buys, ending in a state where we are holding a stock.

We iterate through each day's price and update these two arrays. For each price and for each transaction count `j` from 1 to `k`, we apply the following transitions:
- To update `buy[j]`, we consider either holding the stock we bought previously (`buy[j]`) or buying a stock today. If we buy today, our profit is the profit from `j-1` completed transactions (`sell[j-1]`) minus the current price.
  `buy[j] = max(buy[j], sell[j-1] - price)`
- To update `sell[j]`, we consider either doing nothing (`sell[j]`) or selling the stock we are holding today. If we sell, our profit is the profit from holding the stock for the `j`-th transaction (`buy[j]`) plus the current price.
  `sell[j] = max(sell[j], buy[j] + price)`

An important optimization is to check if `k >= n / 2`. If it is, we can perform as many transactions as we want. The problem then simplifies to 'Best Time to Buy and Sell Stock II', which can be solved in O(n) time.

```java
class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n <= 1 || k == 0) {
            return 0;
        }

        // Optimization: if k is large enough, it's the same as unlimited transactions.
        if (k >= n / 2) {
            int maxProfit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    maxProfit += prices[i] - prices[i - 1];
                }
            }
            return maxProfit;
        }

        int[] sell = new int[k + 1];
        int[] buy = new int[k + 1];
        Arrays.fill(buy, Integer.MIN_VALUE);

        for (int price : prices) {
            for (int j = 1; j <= k; j++) {
                buy[j] = Math.max(buy[j], sell[j - 1] - price);
                sell[j] = Math.max(sell[j], buy[j] + price);
            }
        }

        return sell[k];
    }
}
```
### Algorithm
1. Handle edge cases: if `n <= 1` or `k == 0`, return 0.
2. Apply an optimization: if `k >= n / 2`, the problem is equivalent to unlimited transactions. Solve it in O(n) time by summing all positive price differences `prices[i] - prices[i-1]` and return.
3. Create two arrays, `sell[k+1]` and `buy[k+1]`.
4. Initialize `sell` with all 0s and `buy` with `Integer.MIN_VALUE`.
5. Iterate through each `price` in the `prices` array.
6. Inside this loop, iterate `j` from 1 to `k`.
7. Update the `buy` and `sell` arrays based on the transitions:
   - `buy[j] = max(buy[j], sell[j-1] - price)`
   - `sell[j] = max(sell[j], buy[j] + price)`
8. After iterating through all prices, the answer is `sell[k]`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int MaxProfit(int k, int[] prices) {
        int n = prices.Length;
        int[, ] f = new int[k + 1, 2];
        for (int j = 1; j <= k; ++j) {
            f[j, 1] = -prices[0];
        }
        for (int i = 1; i < n; ++i) {
            for (int j = k; j > 0; --j) {
                f[j, 0] = Math.Max(f[j, 1] + prices[i], f[j, 0]);
                f[j, 1] = Math.Max(f[j - 1, 0] - prices[i], f[j, 1]);
            }
        }
        return f[k, 0];
    }
}
```

### Java

```java
class Solution {
public
  int maxProfit(int k, int[] prices) {
    int n = prices.length;
    int[][] f = new int[k + 1][2];
    for (int j = 1; j <= k; ++j) {
      f[j][1] = -prices[0];
    }
    for (int i = 1; i < n; ++i) {
      for (int j = k; j > 0; --j) {
        f[j][0] = Math.max(f[j][1] + prices[i], f[j][0]);
        f[j][1] = Math.max(f[j - 1][0] - prices[i], f[j][1]);
      }
    }
    return f[k][0];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxProfit(int k, vector<int> &prices) {
    int n = prices.size();
    int f[k + 1][2];
    memset(f, 0, sizeof(f));
    for (int j = 1; j <= k; ++j) {
      f[j][1] = -prices[0];
    }
    for (int i = 1; i < n; ++i) {
      for (int j = k; j; --j) {
        f[j][0] = max(f[j][1] + prices[i], f[j][0]);
        f[j][1] = max(f[j - 1][0] - prices[i], f[j][1]);
      }
    }
    return f[k][0];
  }
};

```

### Python

```python
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int: n = len(prices) if n < 2: return 0  # 3-D dp: n days * k completed transactions * 2 ops buy/sell # my understanding, one transaction, meaning both buy then sell completed dp = [[[ 0 ] * 2 for _ in range ( k + 1 )] for _ in range ( n )] for i in range ( 1 , k + 1 ): dp [ 0 ][ i ][ 1 ] = - prices [ 0 ] # dp[][][ 0/1 ], 1 is buy, 0 is sell for i in range ( 1 , n ): for j in range ( 1 , k + 1 ): dp [ i ][ j ][ 0 ] = max ( dp [ i - 1 ][ j ][ 1 ] + prices [ i ], dp [ i - 1 ][ j ][ 0 ]) # [1] => sell happening <= that day dp [ i ][ j ][ 1 ] = max ( dp [ i - 1 ][ j - 1 ][ 0 ] - prices [ i ], dp [ i - 1 ][ j ][ 1 ]) return dp [ - 1 ][ k ][ 0 ] ############## class Solution : def maxProfit ( self , k : int , prices : List [ int ]) -> int : @ cache def dfs ( i , j , k ): if i >= len ( prices ): return 0 ans = dfs ( i + 1 , j , k ) if k : ans = max ( ans , prices [ i ] + dfs ( i + 1 , j , 0 )) elif j : ans = max ( ans , - prices [ i ] + dfs ( i + 1 , j - 1 , 1 )) return ans return dfs ( 0 , k , 0 ) ############## import heapq import random class Solution ( object ): def findKthLargest ( self , nums , k ): """ :type A: List[int] :type k: int :rtype: int """ def quickselect ( start , end , nums , k ): if start == end : return nums [ start ] mid = partition ( start , end , nums ) if mid == k : return nums [ mid ] elif k > mid : return quickselect ( mid + 1 , end , nums , k ) else : return quickselect ( start , mid - 1 , nums , k ) def partition ( start , end , nums ): p = random . randrange ( start , end + 1 ) pv = nums [ p ] nums [ end ], nums [ p ] = nums [ p ], nums [ end ] mid = start for i in range ( start , end ): if nums [ i ] >= pv : nums [ i ], nums [ mid ] = nums [ mid ], nums [ i ] mid += 1 nums [ mid ], nums [ end ] = nums [ end ], nums [ mid ] return mid return quickselect ( 0 , len ( nums ) - 1 , nums , k - 1 ) def maxProfit ( self , k , prices ): """ :type k: int :type prices: List[int] :rtype: int """ if not prices : return 0 stack = [] heap = [] v = p = 0 n = len ( prices ) ans = 0 while p < n : v = p while v < n - 1 and prices [ v ] >= prices [ v + 1 ]: v += 1 p = v + 1 while p < n and prices [ p ] > prices [ p - 1 ]: p += 1 while stack and prices [ stack [ - 1 ][ 0 ]] > prices [ v ]: _v , _p = stack . pop () heap . append ( prices [ _p - 1 ] - prices [ _v ]) while stack and prices [ stack [ - 1 ][ 1 ] - 1 ] < prices [ p - 1 ]: heap . append ( prices [ stack [ - 1 ][ 1 ] - 1 ] - prices [ v ]) v , _ = stack . pop () stack . append (( v , p )) heap += [ prices [ p - 1 ] - prices [ v ] for v , p in stack ] if len ( heap ) < k : return sum ( heap ) self . findKthLargest ( heap , k ) return sum ( heap [: k ])

```