Best Time to Buy and Sell Stock IV

Problem

You are given an integer k and an array prices, where prices[i] is the price of a stock on day i. You may complete at most k transactions to maximize your profit. A transaction is one buy followed by a later sell, and you may hold at most one share at a time (sell before buying again). You never have to trade. Return the maximum total profit achievable. This is the general form of Stock III, where k was fixed at 2.

Examples

• k = 2, prices = [2, 4, 1] → 2 — buy at 2, sell at 4 for +2; the second transaction adds nothing.
• k = 2, prices = [3, 2, 6, 5, 0, 3] → 7 — buy 2 sell 6 (+4), then buy 0 sell 3 (+3); total 7.
• k = 3, prices = [1, 2, 3, 4, 5] → 4 — the whole rise is a single transaction; the extra allowed transactions go unused.

Constraints

• 0 <= k <= 100
• 0 <= len(prices) <= 1000
• 0 <= prices[i] <= 1000
• At most k non-overlapping transactions.
• Note k can exceed len(prices) // 2. Beyond that cap, extra transactions are useless (each needs at least two days), so the problem degenerates into “unlimited transactions”.

Think about it first

TL;DR

State-machine DP over (day, transactions left, holding?), space-optimized to O(k) rolling arrays, with a greedy shortcut when k is large — O(n·k) time, O(k) space.

The recurrence

Let f(i, t, h) be the most profit obtainable from day i onward with t transactions remaining and h = 1 if holding a share. Charge a transaction on the buy.

f(i, t, 0) = max( f(i+1, t, 0),                # rest, empty-handed
                  f(i+1, t-1, 1) - prices[i] )    # buy today (uses a transaction)
f(i, t, 1) = max( f(i+1, t, 1),                # rest, holding
                  f(i+1, t, 0) + prices[i] )      # sell today
base:  f(n, ., .) = 0  and  f(i, 0, 0) = 0
answer = f(0, k, 0)

Each day is a two-state machine: you either hold a share or you don’t. Resting keeps the state; a buy or sell flips it, and a buy consumes one of the k transactions.

flowchart LR
    NH["Not holding<br/>t left"] -->|"buy: -prices[i]<br/>(uses a transaction)"| H["Holding<br/>t-1 left"]
    H -->|"sell: +prices[i]"| NH
    NH -->|rest| NH
    H -->|rest| H

Approach 1 — Brute-force recursion

Encode the recurrence directly, without a cache. From each day, either rest or take the only legal action for the current holding state, and recurse.

from typing import List

def maxProfit(k: int, prices: List[int]) -> int:
    n = len(prices)

    def f(i: int, t: int, holding: int) -> int:
        if i == n or t == 0:
            return 0
        rest = f(i + 1, t, holding)
        if holding:
            act = prices[i] + f(i + 1, t, 0)          # sell
        else:
            act = -prices[i] + f(i + 1, t - 1, 1)     # buy
        return max(rest, act)

    return f(0, k, 0)

Complexity: exponential, O(2ⁿ) time — every day branches into rest/act and identical (i, t, holding) states are recomputed on many paths. Correct as a specification, but too slow at n = 1000.

Approach 2 — Memoized top-down

The state (i, t, holding) has only n · (k+1) · 2 combinations, each a fixed value. Cache it and the exponential tree collapses to O(n·k) distinct evaluations.

from functools import lru_cache
from typing import List

def maxProfit(k: int, prices: List[int]) -> int:
    n = len(prices)

    @lru_cache(maxsize=None)
    def f(i: int, t: int, holding: int) -> int:
        if i == n or t == 0:
            return 0
        rest = f(i + 1, t, holding)
        if holding:
            act = prices[i] + f(i + 1, t, 0)
        else:
            act = -prices[i] + f(i + 1, t - 1, 1)
        return max(rest, act)

    return f(0, k, 0)

Complexity: O(n·k) time and O(n·k) space (cache + recursion depth up to n). Correct, but deep recursion and cache overhead motivate the tabulated forms.

Approach 3 — Tabulated bottom-up

Fill the table iteratively. Handle the degenerate case up front: a transaction needs at least two days, so if k >= n // 2 you are effectively unconstrained and can greedily bank every upward step (sum each positive daily difference prices[i] - prices[i-1]).

from typing import List

def maxProfit(k: int, prices: List[int]) -> int:
    n = len(prices)
    if n < 2 or k == 0:
        return 0

    if k >= n // 2:                       # effectively unlimited transactions
        return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))

    # dp[t][h] for the current day, filled backward over days
    dp = [[0, 0] for _ in range(k + 1)]
    for i in range(n - 1, -1, -1):
        new = [[0, 0] for _ in range(k + 1)]
        for t in range(1, k + 1):
            new[t][0] = max(dp[t][0], -prices[i] + dp[t - 1][1])   # rest / buy
            new[t][1] = max(dp[t][1],  prices[i] + dp[t][0])       # rest / sell
        dp = new
    return dp[k][0]

Complexity: O(n·k) time; O(k) space for the two small grids (the greedy branch is O(n)/O(1)).

Approach 4 — Space-optimized rolling arrays

Generalize Stock III’s four scalars to k of each. buy[t] is the best balance after buying the t-th share; sell[t] is the best profit after selling it. Sweep days left to right; within a day update t = 1..k, each transition reading only the previous day’s values (and sell[t-1], already finalized for an earlier transaction).

from typing import List

def maxProfit(k: int, prices: List[int]) -> int:
    n = len(prices)
    if n < 2 or k == 0:
        return 0
    if k >= n // 2:
        return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))

    buy = [float("-inf")] * (k + 1)       # buy[t]: balance after t-th buy
    sell = [0] * (k + 1)                  # sell[t]: profit after t-th sell
    for p in prices:
        for t in range(1, k + 1):
            buy[t] = max(buy[t], sell[t - 1] - p)   # buy t-th share
            sell[t] = max(sell[t], buy[t] + p)      # sell t-th share
    return sell[k]

Walkthrough on k = 2, prices = [3, 2, 6, 5, 0, 3] (expected 7). Tracking (buy1, sell1, buy2, sell2):

sell[2] = 7 — buy 2→sell 6 (+4), buy 0→sell 3 (+3).

Complexity: O(n·k) time, O(k) space — the standard production form.

Common pitfalls

• Skipping the k >= n // 2 shortcut: with k = 100 and small n you still get the right answer, but the general trick matters, and more importantly the shortcut prevents wasted O(n·k) work when k is huge relative to n.
• Initializing buy[t] to 0 instead of -inf — that invents a free share and inflates profit on falling prices.
• Off-by-one on sell[t - 1]: the t-th buy is funded by the profit of the previous (t−1) completed transaction, not the current one.
• Handling empty prices / k == 0: return 0 before allocating arrays.

Pattern takeaway

“At most k uses” DPs share one skeleton: state = (position, uses left, small status flag), transition = max(rest, act). Optimize space by collapsing the position axis into rolling arrays indexed by the use-count, and check whether a large budget degenerates the problem into an unbounded, greedy version. That shortcut is often the difference between a passing solution and one that times out.