Best Time to Buy and Sell Stock IV — Hard Problem & Solution

prices[i] is the price of a stock on day i. You may complete at most k transactions, and you must sell before buying again — never holding more than one…

Difficulty: Hard
Topics: Arrays, Dynamic Programming
Asked at: Amazon, Google, Goldman Sachs
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

prices[i] is the price of a stock on day i. You may complete at most k transactions, and you must sell before buying again — never holding more than one share.

Return the maximum profit.

Example 1

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy at 2 and sell at 4.

Example 2

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy at 2, sell at 6; buy at 0, sell at 3.

Example 3

Input: k = 1, prices = [7,6,4,3,1]
Output: 0
Explanation: Prices only fall, so do nothing.

Constraints

1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000

How to solve Best Time to Buy and Sell Stock IV

A rolling DP over days with two arrays indexed by transaction number. Each day either continues the current state or transitions into it, which keeps everything to one pass over days times k.

Approach

Short-circuit: if k >= n / 2, sum every positive day-to-day increase — the cap cannot bind.
Otherwise initialise buy[j] very negative and sell[j] to 0.
For each day and each j, update buy[j] = max(buy[j], sell[j-1] - price) and then sell[j] = max(sell[j], buy[j] + price).
The answer is sell[k].

Why it works

Updating buy[j] before sell[j] on the same day would allow buying and selling on the same day, which is harmless: it contributes zero profit and never beats a real transaction. Each transaction is a buy followed by a later sell, and the arrays track exactly the best balance in each of those states, so the recurrence is complete. The k >= n/2 case matters because at most n/2 disjoint transactions fit in n days.

Complexity

Time — O(n · k)
Space — O(k)

Pitfalls

Without the k >= n / 2 shortcut, a large k makes the DP needlessly slow.
buy[j] must start at a very negative value, not 0, or a phantom free share appears.
sell[j-1] is the balance before the j-th transaction — using sell[j] there double-counts.

Reference solution

Python

from typing import List

def maxProfit(k: int, prices: List[int]) -> int:
    n = len(prices)
    if n == 0 or k == 0:
        return 0
    if k >= n // 2:
        return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))
    NEG = -10 ** 9
    buy = [NEG] * (k + 1)
    sell = [0] * (k + 1)
    for p in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j - 1] - p)
            sell[j] = max(sell[j], buy[j] + p)
    return sell[k]

JavaScript

var maxProfit = function(k, prices) {
    var NEG = -1000000000;
    var n = prices.length;
    if (n === 0 || k === 0) return 0;
    var i, j;
    if (k >= n / 2) {
        var profit = 0;
        for (i = 1; i < n; i++) if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        return profit;
    }
    var buy = [], sell = [];
    for (j = 0; j <= k; j++) { buy.push(NEG); sell.push(0); }
    for (i = 0; i < n; i++) {
        for (j = 1; j <= k; j++) {
            if (sell[j - 1] - prices[i] > buy[j]) buy[j] = sell[j - 1] - prices[i];
            if (buy[j] + prices[i] > sell[j]) sell[j] = buy[j] + prices[i];
        }
    }
    return sell[k];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue