Best Time to Buy and Sell Stock V — Problem & Solution
Best Time to Buy and Sell Stock V solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Best Time to Buy and Sell Stock V is a medium coding problem on arrays and dynamic programming, asked in Amazon and Bloomberg interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Bloomberg
- 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
You are given an array prices, where prices[i] is the price of a stock on day i, and an integer k.
You may make at most k transactions, each of one of two kinds:
- Normal: buy on day
i, sell on a later dayj > i, earningprices[j] - prices[i]. - Short selling: sell on day
i, buy back on a later dayj > i, earningprices[i] - prices[j].
Transactions may not overlap: one must be finished before the next starts, and a new transaction cannot start on the same day the previous one ends.
Return the maximum total profit you can earn.
Example 1
Input: prices = [1,7,9,8,2], k = 2
Output: 14
Explanation: Buy on day 0 at 1 and sell on day 2 at 9 (+8); short on day 3 at 8 and buy back on day 4 at 2 (+6).
Example 2
Input: prices = [12,16,19,19,8,1,19,13,9], k = 3
Output: 36
Explanation: Buy at 12, sell at 19 (+7); short at 19, buy back at 1 (+18); short at 19, buy back at 8 (+11).
Example 3
Input: prices = [5,5], k = 1
Output: 0
Explanation: No transaction can make money.
Constraints
2 <= prices.length <= 10^31 <= prices[i] <= 10^6 (the original allows 10^9; capped here so every profit fits a 32-bit integer)1 <= k <= prices.length / 2
Hints for Best Time to Buy and Sell Stock V
Hint 1
This is "Best Time to Buy and Sell Stock IV" with a second kind of position: holding a short.
Hint 2
Track three states per number of completed transactions: free (no position), long (bought, not yet sold) and short (sold, not yet bought back).
Hint 3
Each day, from yesterday's values: free → long pays
-price, free → short earns+price, long → free earns+priceand short → free pays-price(both completing a transaction). Using only yesterday's values keeps a transaction from opening on the day another closes.
How to solve Best Time to Buy and Sell Stock V
At the end of any day you are in one of three positions — flat, long or short — and what matters for the future is that position plus how many transactions are already done. A DP over days with those states covers every plan.
Approach
- Let
free[c],long[c],short[c]be the best balance withccompleted transactions; start withfree[0] = 0and everything else-∞. - For each price
p, compute new values from the old ones:free[c + 1] = max(free[c + 1], long[c] + p, short[c] - p);long[c] = max(long[c], free[c] - p)andshort[c] = max(short[c], free[c] + p)forc < k. - After the last day, return
max(free[c])overc.
Why it works
Every valid schedule is a sequence of non-overlapping intervals, each opened from the flat state and closed back into it, and the DP tracks exactly the position held on each day. Reading only the previous day's values means a position closed today cannot feed a position opened today, which enforces the no-shared-day rule; opening and closing on the same day is likewise impossible.
Complexity
- Time —
O(n · k) - Space —
O(k)
Pitfalls
- A short sale is a separate state — you cannot model it as a negative long position in the same array.
- Update from the previous day's arrays (or iterate carefully); updating in place lets a transaction close and the next one open on the same day.
- Use 64-bit arithmetic for the
-∞sentinels so-∞ + pcannot wrap around.
Reference solution
Python
from typing import List
def maximumProfit(prices: List[int], k: int) -> int:
NEG = float('-inf')
free = [NEG] * (k + 1)
hold = [NEG] * (k + 1)
short = [NEG] * (k + 1)
free[0] = 0
for p in prices:
nf, nh, ns = free[:], hold[:], short[:]
for c in range(k):
if hold[c] + p > nf[c + 1]:
nf[c + 1] = hold[c] + p
if short[c] - p > nf[c + 1]:
nf[c + 1] = short[c] - p
if free[c] - p > nh[c]:
nh[c] = free[c] - p
if free[c] + p > ns[c]:
ns[c] = free[c] + p
free, hold, short = nf, nh, ns
return int(max(free))Java
public static int maximumProfit(int[] prices, int k) {
final long NEG = Long.MIN_VALUE / 4;
long[] free = new long[k + 1], hold = new long[k + 1], sh = new long[k + 1];
Arrays.fill(free, NEG);
Arrays.fill(hold, NEG);
Arrays.fill(sh, NEG);
free[0] = 0;
for (int p : prices) {
long[] nf = free.clone(), nh = hold.clone(), ns = sh.clone();
for (int c = 0; c < k; c++) {
nf[c + 1] = Math.max(nf[c + 1], Math.max(hold[c] + p, sh[c] - p));
nh[c] = Math.max(nh[c], free[c] - p);
ns[c] = Math.max(ns[c], free[c] + p);
}
free = nf;
hold = nh;
sh = ns;
}
long best = 0;
for (long v : free) best = Math.max(best, v);
return (int) best;
}C++
int maximumProfit(vector<int>& prices, int k) {
const long long NEG = LLONG_MIN / 4;
vector<long long> fr(k + 1, NEG), hold(k + 1, NEG), sh(k + 1, NEG);
fr[0] = 0;
for (int p : prices) {
vector<long long> nf = fr, nh = hold, ns = sh;
for (int c = 0; c < k; c++) {
nf[c + 1] = max(nf[c + 1], max(hold[c] + p, sh[c] - p));
nh[c] = max(nh[c], fr[c] - p);
ns[c] = max(ns[c], fr[c] + p);
}
fr = nf;
hold = nh;
sh = ns;
}
long long best = 0;
for (long long v : fr) best = max(best, v);
return (int) best;
}JavaScript
var maximumProfit = function(prices, k) {
var NEG = -Infinity;
var free = [], hold = [], sh = [];
for (var c = 0; c <= k; c++) { free.push(NEG); hold.push(NEG); sh.push(NEG); }
free[0] = 0;
for (var d = 0; d < prices.length; d++) {
var p = prices[d];
var nf = free.slice(), nh = hold.slice(), ns = sh.slice();
for (var t = 0; t < k; t++) {
if (hold[t] + p > nf[t + 1]) nf[t + 1] = hold[t] + p;
if (sh[t] - p > nf[t + 1]) nf[t + 1] = sh[t] - p;
if (free[t] - p > nh[t]) nh[t] = free[t] - p;
if (free[t] + p > ns[t]) ns[t] = free[t] + p;
}
free = nf; hold = nh; sh = ns;
}
var best = 0;
for (var q = 0; q <= k; q++) if (free[q] > best) best = free[q];
return best;
};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