LeetCode 188 - Best Time to Buy and Sell Stock IV

This problem asks us to maximize the profit from stock trading under a strict constraint: we can perform at most k transactions, where each transaction consists of buying and then later selling one share of the stock.

leetcodehardarraydynamic-programming

LeetCode Problem 188

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem asks us to maximize the profit from stock trading under a strict constraint: we can perform at most k transactions, where each transaction consists of buying and then later selling one share of the stock. We are given an array prices where prices[i] represents the price of the stock on the i-th day. The goal is to return the maximum profit achievable given these constraints.

The input k is an integer between 1 and 100, which limits the number of transactions. The array prices has up to 1000 elements, each between 0 and 1000. This means we cannot use exponential brute-force solutions because prices.length is large enough to make them impractical.

Edge cases to consider include scenarios where k is very large relative to the number of days, or where the array is monotonically increasing or decreasing. If k is larger than half the number of days, it effectively allows unlimited transactions. Similarly, empty arrays or arrays with a single element cannot yield profit.

The main challenge is balancing transaction count with optimal buy-sell timing across the days while staying within k transactions.

Approaches

The brute-force approach would attempt to explore every possible sequence of buy-sell transactions. This can be done recursively by trying all possible buy and sell pairs for each allowed transaction. While correct, it is prohibitively slow: the number of combinations grows exponentially with the length of prices and the number of allowed transactions, making it infeasible for prices.length up to 1000.

The key insight for an optimal solution is to use dynamic programming. We define a state dp[t][d] as the maximum profit achievable using at most t transactions by day d. For each day and transaction count, we have two choices: do nothing, or sell stock on that day, which requires knowing the maximum profit achievable by buying on any previous day. To make this efficient, we maintain a running maximum of dp[t-1][d'] - prices[d'] across previous days d'. This avoids the need for a nested loop over all previous days, reducing the complexity to O(k * n).

When k is larger than n // 2, we can simplify the problem to unlimited transactions. In that case, the solution reduces to summing all positive price differences between consecutive days.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(n*k)) O(n*k) Recursively try all sequences of buy-sell pairs
Optimal DP O(k * n) O(k * n) Uses dynamic programming with running max to avoid nested loops

Algorithm Walkthrough

  1. Check if the prices array is empty or has only one element. If so, return 0 because no profit is possible.
  2. If k is greater than or equal to n // 2 (where n is the length of prices), treat it as unlimited transactions. Iterate through prices and sum all positive differences between consecutive days to get maximum profit.
  3. Initialize a 2D array dp of size (k+1) x n, where dp[t][d] represents the maximum profit with at most t transactions until day d.
  4. For each transaction t from 1 to k, maintain a variable maxDiff initialized to -prices[0]. This represents the maximum value of dp[t-1][d'] - prices[d'] up to the current day.
  5. Iterate over days d from 1 to n-1. Update dp[t][d] as the maximum of dp[t][d-1] (doing nothing) or prices[d] + maxDiff (selling today). Update maxDiff as the maximum of itself or dp[t-1][d] - prices[d].
  6. After filling the table, the result is dp[k][n-1], representing the maximum profit with at most k transactions until the last day.

Why it works: The dp table maintains the invariant that dp[t][d] is the maximum profit achievable using at most t transactions until day d. The running maxDiff efficiently tracks the best buying opportunity for the current transaction count. This ensures all transactions are valid (buy before sell) and the transaction limit k is respected.

Python Solution

from typing import List

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        if n < 2 or k == 0:
            return 0
        
        if k >= n // 2:
            profit = 0
            for i in range(1, n):
                profit += max(0, prices[i] - prices[i-1])
            return profit
        
        dp = [[0] * n for _ in range(k+1)]
        
        for t in range(1, k+1):
            maxDiff = -prices[0]
            for d in range(1, n):
                dp[t][d] = max(dp[t][d-1], prices[d] + maxDiff)
                maxDiff = max(maxDiff, dp[t-1][d] - prices[d])
        
        return dp[k][n-1]

In this implementation, we first handle the trivial cases of empty array or zero transactions. For the unlimited transactions case, we sum all profitable consecutive differences. Otherwise, we build the DP table while maintaining a running maxDiff to optimize the calculation of profit when selling on the current day. The final result is stored at dp[k][n-1].

Go Solution

func maxProfit(k int, prices []int) int {
    n := len(prices)
    if n < 2 || k == 0 {
        return 0
    }
    
    if k >= n/2 {
        profit := 0
        for i := 1; i < n; i++ {
            if prices[i] > prices[i-1] {
                profit += prices[i] - prices[i-1]
            }
        }
        return profit
    }
    
    dp := make([][]int, k+1)
    for t := range dp {
        dp[t] = make([]int, n)
    }
    
    for t := 1; t <= k; t++ {
        maxDiff := -prices[0]
        for d := 1; d < n; d++ {
            dp[t][d] = max(dp[t][d-1], prices[d]+maxDiff)
            maxDiff = max(maxDiff, dp[t-1][d]-prices[d])
        }
    }
    
    return dp[k][n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go solution mirrors the Python version. We initialize the DP slice and handle the unlimited transactions scenario explicitly. The max helper function is used to simplify comparisons. Go requires explicit slice allocation for the 2D DP array, unlike Python.

Worked Examples

Example 1: k = 2, prices = [2,4,1]

t\day 0 1 2
1 0 2 2
2 0 2 2

Step-by-step: On day 1, we buy at 2 and sell at 4, profit = 2. Day 2 is lower price, no better sell, so DP remains 2.

Example 2: k = 2, prices = [3,2,6,5,0,3]

t\day 0 1 2 3 4 5
1 0 0 4 4 4 4
2 0 0 4 4 4 7

Step-by-step: First transaction: buy day 1 at 2, sell day 2 at 6 = 4. Second transaction: buy day 4 at 0, sell day 5 at 3 = 3. Total = 7.

Complexity Analysis

Measure Complexity Explanation
Time O(k * n) We fill a DP table of size k x n and update maxDiff in constant time each iteration
Space O(k * n) DP table stores maximum profit for each transaction count and day

The optimization to unlimited transactions reduces time to O(n) when k >= n/2.

Test Cases

# Provided examples
assert Solution().maxProfit(2, [2,4,1]) == 2  # simple profit
assert Solution().maxProfit(2, [3,2,6,5,0,3]) == 7  # two separate profitable transactions

# Edge cases
assert Solution().maxProfit(0, [1,2,3,4]) == 0  # zero transactions
assert Solution().maxProfit(100, []) == 0  # empty prices
assert Solution().maxProfit(1, [5,4,3,2,1]) == 0  # monotonically decreasing