Best Time to Buy and Sell Stock IV

LeetCode 188: Best Time to Buy and Sell Stock IV Solution & Explanation

Problem Overview

TL;DR: Use a Dynamic Programming approach with space optimization to track the maximum profit achievable for each of the k permitted transactions as we iterate through daily prices.

The LeetCode 188 problem, "Best Time to Buy and Sell Stock IV," asks us to determine the maximum profit possible from trading a stock given a history of daily prices and a strict limit of k completed transactions. A transaction consists of buying and then selling. Importantly, you cannot engage in multiple transactions simultaneously; you must sell your current holding before buying again.

Brute Force Approach for Best Time to Buy and Sell Stock IV

The brute force approach attempts to simulate every possible sequence of buying and selling decisions to find the one that yields the highest profit. This can be modeled as a recursion where, on each day, we have three choices depending on our state: buy (if not holding), sell (if holding), or do nothing (skip the day).

The algorithm would look like this:

1. Define a recursive function solve(day, transactions_remaining, is_holding).
2. Base cases: If day exceeds the price array or transactions_remaining is 0, return 0.
3. Recursive step:
   • If holding stock: Maximize between sell (add current price, decrement transactions) and skip.
   • If not holding: Maximize between buy (subtract current price) and skip.
4. Return the maximum of these paths.

1# Pseudo-code for Brute Force
2def solve(day, k_left, holding):
3    if day >= len(prices) or k_left == 0:
4        return 0
5    
6    # Option 1: Do nothing
7    res = solve(day + 1, k_left, holding)
8    
9    if holding:
10        # Option 2: Sell
11        res = max(res, prices[day] + solve(day + 1, k_left - 1, False))
12    else:
13        # Option 3: Buy
14        res = max(res, -prices[day] + solve(day + 1, k_left, True))
15        
16    return res

Time Complexity: $O(2^n)$
The decision tree branches twice at every step (buy/skip or sell/skip) for n days. This exponential growth makes the solution infeasible for $n$ up to 1000.

Why it fails: The constraints allow up to 1000 days. $2^{1000}$ is an astronomically large number, leading to an immediate Time Limit Exceeded (TLE). Furthermore, this approach recalculates the same states (same day, same k, same holding status) repeatedly.

Algorithm Strategy: Dynamic Programming (DP) Patterns

We will implement an optimized Dynamic Programming solution. While a full 2D DP table dp[k][days] is intuitive, we can optimize space to $O(k)$ because today's values only depend on yesterday's values.

Optimization Note: If $k \ge n/2$ (where $n$ is the number of days), we can make as many transactions as we want because we cannot buy and sell more frequently than every other day. In this specific case, the problem degrades to LeetCode 122: Best Time to Buy and Sell Stock II, which can be solved with a simple greedy approach ($O(n)$ time, $O(1)$ space). Although the general DP solution works for this case too, handling it separately is a common optimization.

General DP Strategy:

1. Initialize two arrays, buy and sell, both of size k+1.
   • buy[j] initializes to $-\infty$ (or a very small number) because buying initially costs money (negative profit).
   • sell[j] initializes to 0.
2. Iterate through each price in the prices array.
3. For each price, iterate through transactions j from 1 to k.
4. Update buy[j]: Maximize between keeping the previous buy[j] (doing nothing) or starting the $j$-th transaction today (sell[j-1] - price).
5. Update sell[j]: Maximize between keeping the previous sell[j] (doing nothing) or completing the $j$-th transaction today (buy[j] + price).
6. The result is sell[k].

Execution Flow

1. Input Check: If prices is empty, return 0.
2. Large K Optimization: If k >= prices.length / 2, run the greedy algorithm (sum all positive price differences) and return the result.
3. Initialization:
   • Create array buy of size k+1 filled with Integer.MIN_VALUE.
   • Create array sell of size k+1 filled with 0.
4. DP Loop (Time): Iterate through each price in prices:
   • Inner Loop (Transactions): Iterate j from 1 to k.
     • Update Buy: buy[j] = max(buy[j], sell[j-1] - price)
       • Logic: Either we keep holding the stock we bought previously for transaction j, or we buy now using the profit from completing transaction j-1.
     • Update Sell: sell[j] = max(sell[j], buy[j] + price)
       • Logic: Either we stay sold (no stock), or we sell the stock we are currently holding for transaction j at the current price.
5. Result: Return sell[k], which represents the maximum profit after at most k transactions.

Proof of Correctness

The algorithm is correct based on the principle of optimality. For the $j$-th transaction on day $i$:

• The optimal decision to hold a stock is derived from the maximum of "holding from day $i-1$" or "buying on day $i$ given the optimal profit of $j-1$ transactions".
• The optimal decision to not hold (sell) is derived from the maximum of "not holding from day $i-1$" or "selling on day $i$ given the optimal profit of the current hold state".

Since we consider all valid transitions (Hold $\to$ Hold, Sold $\to$ Hold, Hold $\to$ Sold, Sold $\to$ Sold) and maximize profit at each step, the final state sell[k] accumulates the maximum possible profit.

Pattern Reuse Notes

The Dynamic Programming pattern used here is directly applicable to several other "Stock" problems on LeetCode. Understanding the state machine (Hold/Sold) is the key to solving all of them.

• LeetCode 121: Best Time to Buy and Sell Stock (Equivalent to $k=1$)
• LeetCode 122: Best Time to Buy and Sell Stock II (Equivalent to $k=\infty$)
• LeetCode 123: Best Time to Buy and Sell Stock III (Equivalent to $k=2$)
• LeetCode 309: Best Time to Buy and Sell Stock with Cooldown (Adds a "Cooldown" state to the DP transition)

Reference Implementation

C++ Solution for LeetCode 188

1#include <vector>
2#include <algorithm>
3#include <climits>
4
5using namespace std;
6
7class Solution {
8public:
9    int maxProfit(int k, vector<int>& prices) {
10        int n = prices.size();
11        if (n == 0) return 0;
12
13        // Optimization for large k: equivalent to infinite transactions
14        if (k >= n / 2) {
15            int max_profit = 0;
16            for (int i = 1; i < n; ++i) {
17                if (prices[i] > prices[i - 1]) {
18                    max_profit += prices[i] - prices[i - 1];
19                }
20            }
21            return max_profit;
22        }
23
24        // DP State
25        // buy[j] represents max profit after j-th buy
26        // sell[j] represents max profit after j-th sell
27        vector<int> buy(k + 1, INT_MIN);
28        vector<int> sell(k + 1, 0);
29
30        for (int price : prices) {
31            for (int j = 1; j <= k; ++j) {
32                // Update buy[j]: either keep holding or buy now using profit from sell[j-1]
33                buy[j] = max(buy[j], sell[j - 1] - price);
34                
35                // Update sell[j]: either keep sold or sell now using profit from buy[j]
36                sell[j] = max(sell[j], buy[j] + price);
37            }
38        }
39
40        return sell[k];
41    }
42};

Java Solution for LeetCode 188

1import java.util.Arrays;
2
3class Solution {
4    public int maxProfit(int k, int[] prices) {
5        int n = prices.length;
6        if (n == 0) return 0;
7
8        // Optimization: if k is large enough, it's the same as infinite transactions allowed
9        if (k >= n / 2) {
10            int maxProfit = 0;
11            for (int i = 1; i < n; i++) {
12                if (prices[i] > prices[i - 1]) {
13                    maxProfit += prices[i] - prices[i - 1];
14                }
15            }
16            return maxProfit;
17        }
18
19        // DP Arrays
20        // buy[j] is max profit with j transactions started (holding stock)
21        // sell[j] is max profit with j transactions completed (not holding stock)
22        int[] buy = new int[k + 1];
23        int[] sell = new int[k + 1];
24
25        // Initialize buy array to very small value as buying reduces profit initially
26        Arrays.fill(buy, Integer.MIN_VALUE);
27
28        for (int price : prices) {
29            for (int j = 1; j <= k; j++) {
30                // Decision: Keep holding or Buy new stock
31                buy[j] = Math.max(buy[j], sell[j - 1] - price);
32                
33                // Decision: Keep not holding or Sell current stock
34                sell[j] = Math.max(sell[j], buy[j] + price);
35            }
36        }
37
38        return sell[k];
39    }
40}

Python Solution for LeetCode 188

1class Solution:
2    def maxProfit(self, k: int, prices: list[int]) -> int:
3        n = len(prices)
4        if n == 0:
5            return 0
6            
7        # Optimization for large k (Infinite transactions case)
8        if k >= n // 2:
9            max_profit = 0
10            for i in range(1, n):
11                if prices[i] > prices[i - 1]:
12                    max_profit += prices[i] - prices[i - 1]
13            return max_profit
14            
15        # DP Initialization
16        # buy[j] tracks max profit after buying for the j-th transaction
17        # sell[j] tracks max profit after selling for the j-th transaction
18        buy = [-float('inf')] * (k + 1)
19        sell = [0] * (k + 1)
20        
21        for price in prices:
22            for j in range(1, k + 1):
23                # We can buy the j-th stock using profit from (j-1)-th sell
24                buy[j] = max(buy[j], sell[j - 1] - price)
25                
26                # We can sell the j-th stock using the hold state of j-th buy
27                sell[j] = max(sell[j], buy[j] + price)
28                
29        return sell[k]