Best Time to Buy and Sell Stock IV

Hard
885.

Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock IV is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Goldman Sachs interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(k, prices) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Best Time to Buy and Sell Stock IV solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Best Time to Buy and Sell Stock IV is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Goldman Sachs interviews.

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

Hints for Best Time to Buy and Sell Stock IV

  1. Hint 1

    Track two running values per transaction count: the best balance while holding a share and while not holding one.

  2. Hint 2

    buy[j] is the best balance after starting the j-th transaction; sell[j] after finishing it.

  3. Hint 3

    When k is at least half the number of days, the cap is no constraint — take every upward move.

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

  1. Short-circuit: if k >= n / 2, sum every positive day-to-day increase — the cap cannot bind.
  2. Otherwise initialise buy[j] very negative and sell[j] to 0.
  3. 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).
  4. 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]

Java

public static int maxProfit(int k, int[] prices) {
    final int NEG = -1000000000;
    int n = prices.length;
    if (n == 0 || k == 0) return 0;
    if (k >= n / 2) {
        int profit = 0;
        for (int i = 1; i < n; i++) if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        return profit;
    }
    int[] buy = new int[k + 1];
    int[] sell = new int[k + 1];
    Arrays.fill(buy, NEG);
    for (int p : prices) {
        for (int j = 1; j <= k; j++) {
            buy[j] = Math.max(buy[j], sell[j - 1] - p);
            sell[j] = Math.max(sell[j], buy[j] + p);
        }
    }
    return sell[k];
}

C++

int maxProfit(int k, vector<int>& prices) {
    const int NEG = -1000000000;
    int n = (int) prices.size();
    if (n == 0 || k == 0) return 0;
    if (k >= n / 2) {
        int profit = 0;
        for (int i = 1; i < n; i++) if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        return profit;
    }
    vector<int> buy(k + 1, NEG), sell(k + 1, 0);
    for (int p : prices) {
        for (int j = 1; j <= k; j++) {
            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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming