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.
- 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 <= 1001 <= prices.length <= 10000 <= prices[i] <= 1000
Hints for Best Time to Buy and Sell Stock IV
Hint 1
Track two running values per transaction count: the best balance while holding a share and while not holding one.
Hint 2
buy[j]is the best balance after starting thej-th transaction;sell[j]after finishing it.Hint 3
When
kis 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
- Short-circuit: if
k >= n / 2, sum every positive day-to-day increase — the cap cannot bind. - Otherwise initialise
buy[j]very negative andsell[j]to 0. - For each day and each
j, updatebuy[j] = max(buy[j], sell[j-1] - price)and thensell[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 / 2shortcut, a largekmakes 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 thej-th transaction — usingsell[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