Best Time to Buy and Sell Stock IV

Difficulty: Hard
Topics: Array, Dynamic Programming
Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

Problem Description

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:


Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: 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
Explanation: 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

1. Problem Deconstruction (500+ words)

Rewrite the Problem

Technical Version
Given an integer array prices of length n and an integer k, we define a transaction as an ordered pair (i, j) such that 0 ≤ i < j < n (buy on day i, sell on day j). A set of transactions is valid if:
- No two transactions overlap: if (i₁, j₁) and (i₂, j₂) are in the set, then either j₁ < i₂ or j₂ < i₁.
- The total number of transactions ≤ k.
  The profit of a transaction (i, j) is prices[j] - prices[i]. The goal is to compute the maximum possible total profit over all valid transaction sets.
Beginner Version
You have a list of daily stock prices. You can make at most k trades. Each trade consists of buying on one day and selling on a later day. You cannot buy again before selling the stock you currently hold. Your aim is to maximize the total profit from these trades. If no profitable trade is possible, you can choose to do nothing.
Mathematical Version
Let p[0], p[1], …, p[n-1] be the price sequence. Find a sequence of indices:
[ i_1 < j_1 < i_2 < j_2 < \dots < i_m < j_m \quad (m \le k) ]
that maximizes:
[ \sum_{t=1}^{m} \big(p[j_t] - p[i_t]\big). ]
Equivalently, define state variables:
- cash[j]: maximum profit after completing j sells (not holding stock).
- hold[j]: maximum profit after completing j buys and currently holding stock.
  Then the recurrence is:
  [ \begin{aligned} \text{hold}[j] &= \max(\text{hold}[j], ;\text{cash}[j-1] - p[i]) \ \text{cash}[j] &= \max(\text{cash}[j], ;\text{hold}[j] + p[i]) \end{aligned} ]
  for each day i and j = 1 \dots k.

Constraint Analysis

1 <= k <= 100
- Limits the number of transactions we need to track. A DP solution with time complexity O(nk) is acceptable (n ≤ 1000 → at most 1e5 operations).
- Hidden edge case: if k ≥ n/2, then the constraint is effectively irrelevant because we cannot have more than n/2 transactions (each requires at least 2 days). This allows an optimization to greedy summation of all positive daily increments.
1 <= prices.length <= 1000
- The problem size is small enough for O(n²k) DP to be borderline (1e8 operations) but O(nk) is safe.
- Implies that recursive brute force (exponential) is infeasible.
0 <= prices[i] <= 1000
- Prices are non‑negative. A zero price means we can buy a stock for free, but selling at zero yields no profit.
- Maximum possible profit per transaction is 1000 (if we buy at 0 and sell at 1000), but total profit is bounded by 1000 × k (≤ 1e5).
- Edge case: a sequence of constant prices (e.g., all zeros) yields zero profit because no profitable transaction exists.

Hidden Edge Cases

k = 0 → no transactions allowed, profit = 0.
n = 1 → cannot complete a single buy‑sell, profit = 0.
Monotonically decreasing prices → best to do nothing (profit = 0).
k very large (k ≥ n/2) → reduce to unlimited transactions, sum all positive daily differences.

2. Intuition Scaffolding

Generate 3 Analogies

Real‑World Metaphor
Imagine you are a concert‑ticket scalper. Each day the ticket price changes. You can buy tickets on low‑price days and sell on high‑price days, but you can only hold one ticket at a time. You have a limit on how many buy‑sell cycles you can perform (e.g., due to time or capital constraints). Your goal is to maximize total profit.
Gaming Analogy
In a fantasy RPG, you trade magic crystals whose price fluctuates daily. You start with no crystals, can buy one when the price is low, sell when high, and repeat. However, you have a limited number of trades because each trade consumes energy. The objective is to maximize your gold after at most k trade cycles.
Math Analogy
Given a sequence of numbers, we want to select at most k disjoint upward “arcs” (intervals [i, j] with p[j] > p[i]) such that the sum of the rises p[j] - p[i] is maximized. This is equivalent to partitioning the sequence into at most k increasing segments and summing the endpoint differences.

Common Pitfalls Section

Greedy on Local Minima/Maxima
Buying at every local minimum and selling at the next local maximum may waste transactions when a single larger swing could be more profitable.
Using All k Transactions Unnecessarily
Forcing exactly k transactions even when some yield losses reduces profit. The optimal might use fewer than k.
Ignoring the “Large k” Optimization
If k ≥ n/2, we can take every profitable daily movement. A naive O(nk) DP would still work but is slower than the O(n) greedy approach.
Overlapping Transactions
Allowing a buy before a previous sell violates the “no simultaneous holdings” rule. DP states must track whether we are holding a stock.
Incorrect DP Initialization
Setting hold[0] = 0 incorrectly implies we can hold a stock without a prior buy. It should be -∞ (or a very small number) because we cannot be in a “holding” state with zero transactions.

3. Approach Encyclopedia

Brute Force (Exponential)

Pseudocode

def bruteForce(prices, k, day, holdings, transactions):
    if day == len(prices) or transactions == k:
        return 0
    if holdings:  # currently holding a stock
        # Option 1: sell today
        profit1 = prices[day] + bruteForce(prices, k, day+1, False, transactions+1)
        # Option 2: skip
        profit2 = bruteForce(prices, k, day+1, True, transactions)
        return max(profit1, profit2)
    else:
        # Option 1: buy today (if we have transactions left)
        profit1 = -prices[day] + bruteForce(prices, k, day+1, True, transactions)
        # Option 2: skip
        profit2 = bruteForce(prices, k, day+1, False, transactions)
        return max(profit1, profit2)

Complexity Proof
At each day we branch into 2–3 choices, leading to a recursion tree of depth n. The number of states is exponential: O(3ⁿ). With n ≤ 1000, this is infeasible.

Visualization

Day:   0    1    2    3    4
Price: 3    2    6    5    0
Brute-force tree (simplified):
Day0: buy / skip
  Day1: sell / skip (if bought) | buy / skip (if not bought)
    ...
Leaves: evaluate profit of each valid transaction set.

Dynamic Programming (O(n²k)) – Naïve DP

Idea
Let dp[t][i] = max profit with at most t transactions up to day i.
Recurrence:
[ dp[t][i] = \max \begin{cases} dp[t][i-1] & \text{skip day } i \ \max_{j < i} \big(dp[t-1][j] + prices[i] - prices[j]\big) & \text{sell on day } i \text{ after buying on day } j \end{cases} ]

Pseudocode

def maxProfit_naive(k, prices):
    n = len(prices)
    if n < 2: return 0
    dp = [[0] * n for _ in range(k+1)]
    for t in range(1, k+1):
        for i in range(1, n):
            dp[t][i] = dp[t][i-1]
            for j in range(i):
                dp[t][i] = max(dp[t][i], dp[t-1][j] + prices[i] - prices[j])
    return dp[k][n-1]

Complexity Proof
Three nested loops: k × n × n → O(k n²). For n=1000, k=100, this is 1e8 operations, borderline but may pass in compiled languages. Space: O(nk).

Visualization

t=1: day i=0..n-1
  For each i, try all j < i as buy day.
t=2: uses dp[1][*] as previous transaction profit.

Optimized DP (O(nk)) – State Machine

Idea
Maintain two arrays:

cash[j]: max profit after j complete transactions (not holding stock).
hold[j]: max profit after j buys and currently holding a stock.

Transition for each price p:

hold[j] = max(hold[j], cash[j-1] - p) // buy stock using profit after j-1 sells.
cash[j] = max(cash[j], hold[j] + p) // sell stock, complete j transactions.

We update j from 1 to k for each price.

Pseudocode

def maxProfit_state_machine(k, prices):
    n = len(prices)
    if n < 2 or k == 0:
        return 0
    # If k is large enough, use greedy
    if k >= n // 2:
        return sum(max(prices[i+1] - prices[i], 0) for i in range(n-1))
    
    hold = [-float('inf')] * (k+1)
    cash = [0] * (k+1)
    
    for p in prices:
        for j in range(1, k+1):
            hold[j] = max(hold[j], cash[j-1] - p)
            cash[j] = max(cash[j], hold[j] + p)
    return cash[k]

Complexity Proof
Two nested loops: n × k → O(nk). Space: O(k).

Visualization

Prices: [3,2,6,5,0,3], k=2
Initialize: hold = [-∞, -∞, -∞]; cash = [0, 0, 0]

Day0 p=3:
  j=1: hold[1]=max(-∞, 0-3)=-3; cash[1]=max(0, -3+3)=0
  j=2: hold[2]=max(-∞, 0-3)=-3; cash[2]=max(0, -3+3)=0
Day1 p=2:
  j=1: hold[1]=max(-3, 0-2)=-2; cash[1]=max(0, -2+2)=0
  j=2: hold[2]=max(-3, 0-2)=-2; cash[2]=max(0, -2+2)=0
Day2 p=6:
  j=1: hold[1]=max(-2, 0-6)=-2; cash[1]=max(0, -2+6)=4
  j=2: hold[2]=max(-2, 4-6)=-2; cash[2]=max(0, -2+6)=4
Day3 p=5:
  j=1: hold[1]=max(-2, 0-5)=-2; cash[1]=max(4, -2+5)=4
  j=2: hold[2]=max(-2, 4-5)=-1; cash[2]=max(4, -1+5)=4
Day4 p=0:
  j=1: hold[1]=max(-2, 0-0)=0; cash[1]=max(4, 0+0)=4
  j=2: hold[2]=max(-1, 4-0)=4; cash[2]=max(4, 4+0)=4
Day5 p=3:
  j=1: hold[1]=max(0, 0-3)=0; cash[1]=max(4, 0+3)=4
  j=2: hold[2]=max(4, 4-3)=4; cash[2]=max(4, 4+3)=7
Result: cash[2]=7

4. Code Deep Dive

Line‑by‑Line Annotations

def maxProfit(k, prices):
    n = len(prices)
    # Edge cases: no profit possible
    if n < 2 or k == 0:
        return 0
    # Optimization for large k (unlimited transactions)
    if k >= n // 2:
        # Sum all positive daily differences
        return sum(max(prices[i+1] - prices[i], 0) for i in range(n-1))
    
    # hold[j] = max profit after j buys and currently holding a stock
    # Initialized to -inf because we cannot be in a holding state without a buy
    hold = [-float('inf')] * (k+1)
    # cash[j] = max profit after j complete transactions (not holding)
    # cash[0] = 0 (no transactions, no stock)
    cash = [0] * (k+1)
    
    for p in prices:
        # Update states for each transaction count j=1..k
        for j in range(1, k+1):
            # Option 1: keep holding, or buy today using profit after j-1 sells
            hold[j] = max(hold[j], cash[j-1] - p)
            # Option 2: keep cash, or sell today using current holding state
            cash[j] = max(cash[j], hold[j] + p)
    
    # The answer is the maximum profit after k complete transactions
    return cash[k]

Edge Case Handling

Example 1: k=2, prices=[2,4,1]
- n=3, k < n//2 (since 2 < 1.5? Actually 3//2=1, so k=2 >1, but we don’t trigger the greedy branch because k is not >= n//2? Wait: n//2 = 1, k=2 >=1, so we would use greedy? But greedy would sum positive differences: (4-2)=2, (1-4)=-3 → sum = 2. That matches the correct answer. So it works.
- The DP yields the same: cash[2]=2.
Example 2: k=2, prices=[3,2,6,5,0,3]
- Greedy not triggered because n//2=3, k=2 < 3. DP proceeds as visualized above, yielding 7.
Zero prices: k=1, prices=[0,0,0]
- hold[1] remains negative, cash[1]=0 → profit 0.
Decreasing sequence: k=1, prices=[5,4,3,2]
- hold[1] becomes -5, -4, -3, -2; cash[1] remains 0 → profit 0.

5. Complexity War Room

Hardware‑Aware Analysis

Time: O(nk) with n≤1000, k≤100 → ≤ 1e5 iterations. On a modern CPU (~3 GHz), each iteration takes a few cycles → total time < 1 ms.
Space: O(k) → two arrays of size 101 (k+1) each. At 8 bytes per float, that’s ~1.6 KB, easily fitting in L1 cache (32–64 KB).
Memory Bandwidth: Sequential access patterns are cache‑friendly, minimizing latency.

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force (recursive)	`O(3ⁿ)`	`O(n)`	9/10 (clear logic)	❌ Fails for n>20
Naïve DP (`O(n²k)`)	`O(n²k)`	`O(nk)`	7/10 (nested loops)	⚠️ Borderline for max constraints
State‑Machine DP (`O(nk)`)	`O(nk)`	`O(k)`	8/10 (requires state explanation)	✅ Recommended
Greedy (large `k`)	`O(n)`	`O(1)`	10/10 (simple sum)	✅ Must‑know optimization

6. Pro Mode Extras

Variants Section

k = 1 (LeetCode 121)

Track minimum price and maximum profit:

min_price = float('inf')
max_profit = 0
for p in prices:
    min_price = min(min_price, p)
    max_profit = max(max_profit, p - min_price)

k = 2 (LeetCode 123)
- Extend state machine to 4 states: buy1, sell1, buy2, sell2.
- Alternatively, split the array at each point and solve two k=1 problems.
With Transaction Fee (LeetCode 714)
- Modify the sell transition: cash = max(cash, hold + p - fee).
With Cooldown (LeetCode 309)
- Introduce an extra state cooldown or shift the buy transition by one day.
Arbitrary k with Space‑Optimized DP
- The state‑machine solution already uses O(k) space.

Interview Cheat Sheet

First Step: Always ask about k relative to n. Mention the greedy optimization for k ≥ n/2.
Second Step: Define DP states clearly: “We track the best profit after j transactions, separated into holding and not‑holding states.”
Third Step: Write the transition equations and justify the update order.
Fourth Step: Walk through a small example to verify correctness.
Fifth Step: State time/space complexity and note hardware efficiency.

Common Pitfalls to Avoid

Forgetting to initialize hold with -∞.
Updating cash[j] before hold[j] (if order matters for your explanation).
Not handling the case k=0 or n<2.
Missing the large‑k optimization (though not required for AC, it shows depth).

Final Optimization Note
If k is very large (e.g., k ≥ 10⁹), the greedy branch is essential. In this problem, k ≤ 100, so the DP is sufficient, but mentioning the greedy branch demonstrates proactive thinking.

#188 - Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock IV

Problem Description

Solution

1. Problem Deconstruction (500+ words)

Rewrite the Problem

Constraint Analysis

2. Intuition Scaffolding

Generate 3 Analogies

Common Pitfalls Section

3. Approach Encyclopedia

Brute Force (Exponential)

Dynamic Programming (O(n²k)) – Naïve DP

Optimized DP (O(nk)) – State Machine

4. Code Deep Dive

Line‑by‑Line Annotations

5. Complexity War Room

Hardware‑Aware Analysis

Industry Comparison Table

6. Pro Mode Extras

Variants Section

Interview Cheat Sheet