Best k Stock Trades
Problem
You may complete at most k non-overlapping buy-sell trades on a daily price series. Return the maximum total profit.
Input
k = 2, prices = [3,2,6,5,0,3]Output
7Generalize the two-trade trick: maintain best cost b[t] and best profit s[t] for each trade index t = 1..k. Update b[t] using s[t−1] − price, then update s[t] using price − b[t].
def max_profit(k, prices):
if not prices or k == 0: return 0
b = [float('inf')] * (k + 1)
s = [0] * (k + 1)
for p in prices:
for t in range(1, k + 1):
b[t] = min(b[t], p - s[t-1])
s[t] = max(s[t], p - b[t])
return s[k]function maxProfit(k, prices) {
if (!prices.length || k === 0) return 0;
const b = new Array(k + 1).fill(Infinity);
const s = new Array(k + 1).fill(0);
for (const p of prices) {
for (let t = 1; t <= k; t++) {
b[t] = Math.min(b[t], p - s[t-1]);
s[t] = Math.max(s[t], p - b[t]);
}
}
return s[k];
}class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length == 0 || k == 0) return 0;
int[] b = new int[k + 1];
int[] s = new int[k + 1];
Arrays.fill(b, Integer.MAX_VALUE);
for (int p : prices) {
for (int t = 1; t <= k; t++) {
b[t] = Math.min(b[t], p - s[t-1]);
s[t] = Math.max(s[t], p - b[t]);
}
}
return s[k];
}
}int maxProfit(int k, vector<int>& prices) {
if (prices.empty() || k == 0) return 0;
vector<int> b(k + 1, INT_MAX), s(k + 1, 0);
for (int p : prices) {
for (int t = 1; t <= k; t++) {
b[t] = min(b[t], p - s[t-1]);
s[t] = max(s[t], p - b[t]);
}
}
return s[k];
}