Skip to main content

188 - Best Time to Buy and Sell Stock IV

Difficulty: Hard | Pattern: Dynamic Programming | Company tags: Amazon, Google, Goldman Sachs

Problem Statement​

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: each transaction is a buy followed by a sell.

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

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2  (buy at 2, sell at 4)

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7  (buy at 2 sell at 6 = 4, buy at 0 sell at 3 = 3)

Approach: DP — O(kn), O(k)​

Key insight: If k >= n//2, unlimited transactions — use greedy. Otherwise, dp[j] = max profit with j transactions. Track best_buy[j] = best price to have bought with j-1 sells complete.

def maxProfit(k: int, prices: list[int]) -> int:
    n = len(prices)
    if not prices or k == 0:
        return 0
    
    # If k >= n//2, unlimited transactions
    if k >= n // 2:
        return sum(max(0, prices[i+1] - prices[i]) for i in range(n-1))
    
    # dp[j] = max profit using exactly (up to) j transactions
    buy = [float('-inf')] * (k + 1)  # best "have bought" state
    sell = [0] * (k + 1)             # best "have sold" state
    
    for price in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j-1] - price)
            sell[j] = max(sell[j], buy[j] + price)
    
    return sell[k]

Dry Run​

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

Start: buy = [-inf, -inf], sell = [0, 0] (indices for j=1,2). For each price we update, in order, buy[j] = max(buy[j], sell[j-1] - price) then sell[j] = max(sell[j], buy[j] + price).

Reading the state: buy[j] is the best profit while holding the stock during the j-th transaction (a negative number = cost paid so far); sell[j] is the best profit after closing up to j transactions.

pricebuy[1]sell[1]buy[2]sell[2]what changed
3-30-30first buy at 3 sets the holding cost
2-20-20cheaper buy at 2 improves both buys
6-24-24sell at 6 → profit 4 in each transaction
5-24-14buy[2] improves: sell[1]−5 = 4−5 = −1 (re-enter after 1st sell)
00444buy[1]=−0; buy[2]=sell[1]−0=4 (already banked 4, now holding for free)
30447sell[2]=buy[2]+3 = 4+3 = 7 (banked 4, plus 3 from 0→3)

Final answer sell[2] = 7 — matches: buy@2 sell@6 (=4), then buy@0 sell@3 (=3).

Edge Cases​

  • k >= n//2: treat as unlimited transactions
  • Empty or single price → 0
  • All decreasing → 0

Complexity​

  • Time: O(k × n)
  • Space: O(k)