Best Time to Buy and Sell Stock IV
Problem
Given an integer k and an array prices where prices[i] is the price of a stock on day i, return the maximum profit achievable with at most k transactions, where each transaction consists of buying and then selling one share of the stock.
- 0 ≤ k ≤ 100
- 0 ≤ prices.length ≤ 1000
- 0 ≤ prices[i] ≤ 1000
Example
k = 2, prices = [3,2,6,5,0,3]7The optimal strategy is to buy on day 1 (price = 2) and sell on day 2 (price = 6), profit = 4, then buy on day 4 (price = 0) and sell on day 5 (price = 3), profit = 3, for a total profit of 7. The algorithm explores states defined by day index, holding status, and remaining transactions. It recursively decides whether to buy, sell, or skip each day, caching results to avoid redundant calculations.
Approach
Straightforward Solution
A brute-force approach tries all possible sequences of buy and sell actions, leading to exponential time complexity due to combinatorial explosion of choices. Without memoization, exploring all buy/sell sequences leads to O(3^(n)) behavior due to branching choices at each day.
Core Observation
The problem requires maximizing profit with at most k buy-sell pairs, where each decision depends on whether a stock is currently held and how many transactions remain. This naturally forms a stateful decision process with overlapping subproblems.
Path to Optimal
Recognizing the problem's optimal substructure and overlapping subproblems suggests Dynamic Programming. Modeling the problem as a state machine with parameters (day, holding status, remaining transactions) allows recursive exploration with memoization. The key insight is that each state can be solved optimally by considering the best among skipping, buying, or selling actions, and caching results prevents redundant work.
Optimal Approach
Use a top-down DP with memoization. Define a recursive function dp(i, holding, remain) that returns the maximum profit achievable starting from day i, with holding indicating if a stock is currently held, and remain the number of transactions left. At each state, compute the max profit by choosing to skip, buy (if not holding), or sell (if holding), and memoize the result. The answer is dp(0, False, k).
Time
O(n * k * 2)
There are n days, k possible remaining transactions, and 2 holding states, resulting in O(n*k*2) unique states. Each state is computed once and memoized, so total time is O(n*k).
Space
O(n * k * 2)
The memoization dictionary stores results for each unique state tuple (day, holding, remaining transactions), leading to O(n*k) auxiliary space. This excludes input and output space.
Pattern Spotlight
Dynamic Programming (State Machine)
When a problem involves sequential decisions with limited states (like holding/not holding and transaction counts), model it as a state machine and use DP to explore all valid paths efficiently by caching overlapping subproblems.
Solution
| 1 | class Solution: |
| 2 | def maxProfit(self, k: int, prices: List[int]) -> int: |
| 3 | memo = {} |
| 4 | |
| 5 | def dp(i, holding, remain): |
| 6 | if i == len(prices) or remain == 0: |
| 7 | return 0 |
| 8 | |
| 9 | key = (i, holding, remain) |
| 10 | if key in memo: |
| 11 | return memo[key] |
| 12 | |
| 13 | ans = dp(i + 1, holding, remain) |
| 14 | |
| 15 | if holding: |
| 16 | ans = max(ans, prices[i] + dp(i + 1, False, remain - 1)) |
| 17 | else: |
| 18 | ans = max(ans, -prices[i] + dp(i + 1, True, remain)) |
| 19 | |
| 20 | memo[key] = ans |
| 21 | return ans |
| 22 | |
| 23 | return dp(0, False, k) |
Step-by-Step Solution
Cache Computed States to Avoid Redundant Computation
| 3 | memo = {} |
Objective
To store results of subproblems defined by day, holding status, and remaining transactions to prevent exponential recomputation.
Key Insight
Memoization transforms the naive exponential recursion into polynomial time by caching the results of each unique state. Since the problem's state space is defined by three parameters, caching results keyed by these parameters ensures each state is solved once, enabling efficient reuse.
Interview Quick-Check
Core Logic
Memoization uses a dictionary keyed by (day, holding, remaining transactions) to store and retrieve computed results, preventing redundant recursive calls.
Common Pitfalls & Bugs
Failing to memoize leads to exponential time complexity due to repeated exploration of identical states.
Recursively Explore All Trading Decisions with State Parameters
| 5 | def dp(i, holding, remain): |
| 6 | if i == len(prices) or remain == 0: |
| 7 | return 0 |
| 9 | key = (i, holding, remain) |
| 10 | if key in memo: |
| 11 | return memo[key] |
| 13 | ans = dp(i + 1, holding, remain) |
| 15 | if holding: |
| 16 | ans = max(ans, prices[i] + dp(i + 1, False, remain - 1)) |
| 17 | else: |
| 18 | ans = max(ans, -prices[i] + dp(i + 1, True, remain)) |
| 20 | memo[key] = ans |
| 21 | return ans |
Objective
To compute the maximum profit from day i onward, considering whether currently holding stock and how many transactions remain.
Key Insight
The recursive function models the problem as a state machine with three parameters. At each state, it considers skipping the day, buying if not holding, or selling if holding. This exhaustive exploration ensures all valid trading sequences are considered. The max operation selects the optimal choice, and memoization guarantees efficiency.
Interview Quick-Check
Core Logic
At each state, the algorithm chooses the best among skipping, buying (if not holding), or selling (if holding), recursively computing future profits and caching results. Memoization check ensures we skip already computed states.
State & Boundaries
Base cases occur when all days are processed or no transactions remain, returning zero profit. The memo ensures base cases aren’t repeatedly recomputed.
Common Pitfalls & Bugs
Incorrectly decrementing transactions on buy instead of sell leads to wrong results. Forgetting to memoize the computed answer causes exponential blowup.
Start Dynamic Programming From the Initial State
| 23 | return dp(0, False, k) |
Objective
Begin the recursive DP from day 0 with an empty portfolio and the full transaction budget.
Key Insight
All profit calculations flow from this single starting state where no stock is held and all k transactions are still available.
Interview Quick-Check
Core Logic
Stock IV DP always begins at day 0 with holding = False and remain = k.
Line Analysis
This solution has 7 Critical lines interviewers watch for.
if key in memo:Check if the current state has been computed before.
This lookup prevents redundant recursive calls by reusing previously computed results, crucial for reducing time complexity from exponential to polynomial.
ans = max(ans, prices[i] + dp(i + 1, False, remain - 1))Calculate profit by selling the stock today and decrementing remaining transactions.
Selling realizes profit by adding the current price and consumes one transaction, transitioning to not holding state for future decisions.
ans = max(ans, -prices[i] + dp(i + 1, True, remain))Calculate profit by buying the stock today without decrementing transactions.
Buying costs the current price and transitions to holding state, but does not reduce transaction count since a transaction completes only upon selling.
memo = {}Initialize memoization dictionary to cache computed states.
This dictionary is essential to store results of subproblems keyed by state, enabling the DP to avoid redundant computations and achieve polynomial time complexity.
if i == len(prices) or remain == 0:Check base cases: if all days processed or no transactions remain, return zero profit.
These termination conditions prevent infinite recursion and correctly represent that no further profit can be made beyond these points.
return memo[key]Return the cached result for the current state if available.
Returning cached results immediately prunes the recursion tree, ensuring each state is solved once and improving efficiency dramatically.
memo[key] = ansCache the computed maximum profit for the current state.
Memoizing the result ensures that future calls with the same state return instantly, preventing exponential recomputation.
def dp(i, holding, remain):Define the recursive DP function with parameters for day, holding status, and remaining transactions.
This function encapsulates the entire state space of the problem, allowing systematic exploration of all trading decisions with clear state representation.
key = (i, holding, remain)Create a key tuple representing the current state for memoization.
The key uniquely identifies the current subproblem, enabling efficient caching and retrieval of computed results.
else:Update the answer with the maximum profit between skipping and selling.
Selecting the maximum ensures the algorithm chooses the optimal action at this state, embodying the principle of optimal substructure.
return ansReturn the maximum profit computed for the current state.
Returning the cached optimal profit completes the recursive step and propagates the solution up the call stack.
return 0Return zero profit for base cases.
Returning zero here correctly signals that no profit is possible when no days or transactions remain, forming the foundation for recursive profit calculations.
ans = dp(i + 1, holding, remain)Calculate profit by skipping the current day and maintaining the current state.
This option preserves the current holding and transaction count, representing the choice to do nothing and wait for a better opportunity.
if holding:Check if currently holding a stock to decide possible actions.
Holding status determines whether selling or buying is valid, guiding the recursive decision tree.
return dp(0, False, k)Start the DP from the initial state: first day, not holding stock, all transactions available.
This initializes the DP search from day 0 with no stock held and the full number of allowed transactions, launching the recursive exploration of all valid trading decisions.
Test Your Understanding
Why does the transaction count decrement only when selling, not when buying?
Because a transaction is defined as a complete buy-sell pair. Buying initiates a transaction but does not complete it, so the count of remaining transactions only decreases upon selling.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Best Time to Buy and Sell Stock IV from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Best Time to Buy and Sell Stock IV drill