Best Time to Buy and Sell Stock IV

Solving tips

This is Stock III generalized: state is (day, transactions left, holding), transition is max(rest, act) with the transaction charged on the buy.
Add the k >= n//2 shortcut up front; a transaction needs two days, so beyond that cap it degenerates to unlimited trading (greedy sum of positive daily diffs).
Space-optimize to buy[t]/sell[t] rolling arrays; the t-th buy is funded by sell[t-1], the previous completed transaction, not the current one.
Target O(n*k) time, O(k) space; seed buy[] to negative infinity and handle empty prices or k==0 before allocating.

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 one clean transaction; 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

Hint 1

This is Stock III with `k` instead of `2`. Carry the same state: how many transactions remain, and whether you currently hold a share. Each day you rest or act.

Hint 2

A single transaction spans at least two days (buy one day, sell a later day). So if `k >= len(prices) // 2`, you can never be limited by `k` — you may as well grab every upward move. That special case collapses to a simple greedy sum and avoids a huge `k`.

Hint 3

Otherwise run the DP over days and `t = 1..k`. Keep, for each `t`, the best "just bought the t-th share" balance and the best "just sold the t-th share" profit, updating both once per day. The answer is the best-sold value at `t = k`, which needs only O(k) rolling storage.

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)

Approach 1 — Brute-force recursion

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

from typing import List

class Solution:
    def maxProfit(self, 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. Fine as a specification, useless at n = 1000.

Approach 2 — Memoized top-down

The insight: the state (i, t, holding) has only n · (k+1) · 2 combinations, and each is 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

class Solution:
    def maxProfit(self, 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

The insight: fill the table iteratively. Also 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 (Kadane-style sum of positive daily differences — grab each prices[i] - prices[i-1] whenever it is positive).

from typing import List

class Solution:
    def maxProfit(self, 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

The insight: generalize Stock III’s four scalars to k of each. buy[t] = best balance after buying the t-th share; sell[t] = 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

class Solution:
    def maxProfit(self, 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):

price	buy1	sell1	buy2	sell2
3	−3	0	−3	0
2	−2	0	−2	0
6	−2	4	−2	4
5	−2	4	−1	4
0	0	4	4	4
3	0	4	4	7

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 always check whether a large budget degenerates the problem into an unbounded/greedy version — recognizing that shortcut is often the difference between a passing and a timing-out solution.