LeetCode 188: Best Time to Buy and Sell Stock IV

Problem Restatement

We are given an integer k and an array prices.

prices[i] is the stock price on day i.

We need to find the maximum profit possible with at most k transactions. One transaction means buying once and selling once. We cannot hold more than one stock at the same time, so we must sell before buying again. The official statement asks for the maximum profit with at most k transactions.

Input and Output

Example function shape:

def maxProfit(k: int, prices: list[int]) -> int:
    ...

Examples

Example 1:

k = 2
prices = [2, 4, 1]

Buy at price 2, sell at price 4.

Profit:

4 - 2 = 2

There is no better second transaction.

Answer:

2

Example 2:

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

One good plan is:

Buy at 2, sell at 6 -> profit 4
Buy at 0, sell at 3 -> profit 3

Total profit:

4 + 3 = 7

Answer:

7

First Thought: Try All Transactions

A brute force search could try every possible buy day and sell day for every transaction.

For one transaction, this already means many pairs.

For multiple transactions, we also need to decide where the next transaction starts.

This quickly becomes too slow because every choice creates more choices.

We need to reuse subproblem results.

Key Insight

At any point, our state has two important parts:

For each transaction count t, we track two best values:

A sell completes one transaction.

So when we sell for transaction t, we come from buy[t].

When we buy for transaction t, we come from sell[t - 1].

Algorithm

Use dynamic programming with arrays of size k + 1.

Initialize:

buy[t] = -infinity
sell[t] = 0

Then for every price:

1. For every transaction number t from 1 to k.
2. Update the best buy state:

buy[t] = max(buy[t], sell[t - 1] - price)

3. Update the best sell state:

sell[t] = max(sell[t], buy[t] + price)

At the end, sell[k] is the best profit with at most k transactions.

Large k Optimization

If k is at least half the number of days, then the transaction limit stops mattering.

With n days, the maximum number of useful transactions is at most:

n // 2

because each transaction needs at least one buy day and one later sell day.

So when:

k >= len(prices) // 2

we can solve it like unlimited transactions: add every positive price increase.

profit += max(0, prices[i] - prices[i - 1])

Correctness

For each t, buy[t] stores the best profit possible after processing the current day while holding one stock and using at most t transactions.

There are two ways to reach this state.

We either already held a stock from an earlier day, so buy[t] stays the same, or we buy today after having completed at most t - 1 transactions, giving:

sell[t - 1] - price

So the update for buy[t] is correct.

For sell[t], there are also two ways to reach the state.

We either already held no stock, so sell[t] stays the same, or we sell today from a holding state, completing transaction t, giving:

buy[t] + price

So the update for sell[t] is correct.

The algorithm processes prices in chronological order, so every buy happens before its matching sell. Since buying uses sell[t - 1], transactions cannot overlap.

At the end, the best valid result must hold no stock, because unsold stock does not contribute profit. Therefore, sell[k] is the maximum profit with at most k transactions.

Complexity

For the unlimited-transactions shortcut:

Implementation

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:
            profit = 0

            for i in range(1, n):
                if prices[i] > prices[i - 1]:
                    profit += prices[i] - prices[i - 1]

            return profit

        buy = [float("-inf")] * (k + 1)
        sell = [0] * (k + 1)

        for price in prices:
            for t in range(1, k + 1):
                buy[t] = max(buy[t], sell[t - 1] - price)
                sell[t] = max(sell[t], buy[t] + price)

        return sell[k]

Code Explanation

This handles inputs where no profit can be made:

if n < 2 or k == 0:
    return 0

This handles the unlimited-transactions case:

if k >= n // 2:

When transactions are effectively unlimited, every upward price movement can be collected.

The DP arrays are:

buy = [float("-inf")] * (k + 1)
sell = [0] * (k + 1)

buy[t] starts at negative infinity because holding a stock before buying is impossible.

sell[t] starts at 0 because doing nothing gives zero profit.

For every price, we update all transaction counts:

for price in prices:
    for t in range(1, k + 1):

This line decides whether buying today improves the holding state:

buy[t] = max(buy[t], sell[t - 1] - price)

This line decides whether selling today improves the non-holding state:

sell[t] = max(sell[t], buy[t] + price)

Finally:

return sell[k]

returns the best profit after at most k transactions while holding no stock.

Testing

def run_tests():
    s = Solution()

    assert s.maxProfit(2, [2, 4, 1]) == 2
    assert s.maxProfit(2, [3, 2, 6, 5, 0, 3]) == 7
    assert s.maxProfit(0, [1, 3, 5]) == 0
    assert s.maxProfit(2, [7, 6, 4, 3, 1]) == 0
    assert s.maxProfit(100, [1, 2, 3, 4, 5]) == 4
    assert s.maxProfit(1, [3, 2, 6, 5, 0, 3]) == 4

    print("all tests passed")

run_tests()

Test meaning: