#188

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Best Time to Buy and Sell Stock IV

Determine the maximum profit from at most k stock transactions using state transition dynamic programming on an array of prices.

array dynamic programming

Problem Statement

You are given an integer array prices where prices[i] represents the price of a stock on day i, along with an integer k. You may perform at most k transactions, where each transaction consists of buying one share and later selling it.

Your goal is to maximize the total profit by strategically choosing which days to buy and sell. You cannot hold more than one share at a time, meaning you must sell before initiating a new purchase, and the solution must account for optimal transitions across multiple allowed transactions.

Examples

Example 1

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

Output: 2

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

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

Solution Approach

Dynamic Programming State Definition

Define two DP arrays: hold[t] for the maximum profit holding a stock after t transactions, and cash[t] for maximum profit without holding a stock after t transactions. Initialize appropriately and update each day using state transitions based on buy or sell actions.

Iterative State Transitions

For each day, iterate through transactions 1 to k and update hold[t] as max(hold[t], cash[t-1] - price) and cash[t] as max(cash[t], hold[t] + price). This ensures correct sequencing and prevents multiple simultaneous holdings, directly addressing the problem's main failure mode.

Handling Large k Optimization

If k exceeds prices.length / 2, treat it as unlimited transactions to simplify calculations. This reduces the DP complexity and avoids unnecessary state tracking, while still adhering to the state transition logic required for smaller k values.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n*k) for standard DP updates or O(n) if k >= n/2 using unlimited transaction optimization. Space complexity is O(k) for compressed DP arrays holding only the last day states.

What Interviewers Usually Probe

Expect clear DP state definition and correct transitions between hold and cash arrays.
Clarify handling of edge cases where k is very large relative to the number of days.
Explain why multiple simultaneous transactions are invalid and how DP enforces this.

Common Pitfalls or Variants

Common pitfalls

Attempting to buy and sell on the same day without proper DP transitions.
Not optimizing for cases where k is large, leading to unnecessary computation.
Incorrect initialization of hold and cash arrays causing off-by-one or negative profits.

Follow-up variants

Unlimited transactions version where k is effectively infinite, simplifying DP updates.
Single transaction (k=1) version reduces to simple max profit calculation.
Transaction fee variant where each sell reduces profit, requiring adjusted state transitions.

FAQ

What is the main pattern to solve Best Time to Buy and Sell Stock IV?

The problem is solved using state transition dynamic programming, tracking hold and cash states across k transactions for each day.

Can I perform multiple transactions simultaneously?

No, you must sell before buying again; the DP approach enforces this constraint in its state transitions.

What happens if k is larger than half the number of days?

Treat k as unlimited, simplifying the DP to iterate through prices with max profit updates for each day.

How do I initialize DP arrays for this problem?

Initialize hold[t] with -infinity and cash[t] with 0 for all t, ensuring correct first transaction calculations.

What are common mistakes in this DP approach?

Failing to update transactions sequentially, mismanaging hold/cash states, or ignoring large k optimizations are frequent errors.

terminal

Solution

Solution 1: Memoization Search

We design a function $dfs(i, j, k)$ to represent the maximum profit that can be obtained when starting from day $i$, completing at most $j$ transactions, and holding the stock with the current state $k$ (not holding the stock is represented by $0$, and holding the stock is represented by $1$). The answer is $dfs(0, k, 0)$.

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            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)

Solution 2: Dynamic Programming

We can also use dynamic programming to define $f[i][j][k]$ as the maximum profit that can be obtained when completing at most j transactions (here we define the number of transactions as the number of purchases), and holding the stock with the current state k on the i-th day. The initial value of $f[i][j][k]$ is 0. The answer is $f[n - 1][k][0]$.

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            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)

Solution 3

#### Python3

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            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)

Continue Practicing

#198 house robber #174 dungeon game #213 house robber ii