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
PreviewRecognizing 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…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse 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…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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
To compute the maximum profit from day i onward, considering whether currently holding stock and how many transactions remain.
Start Dynamic Programming From the Initial State
Begin the recursive DP from day 0 with an empty portfolio and the full transaction budget.
2 more steps with full analysis available on Pro.
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.
Full line-by-line criticality + rationale for all 15 lines available on Pro.
Test Your Understanding
Why does the transaction count decrement only when selling, not when buying?
See the answer with Pro.
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