188. 买卖股票的最佳时机 IV
题目描述
输入整数 k 和数组 prices，prices[i] 是某只股票第 i 天的价格。
一笔交易指先买入一次、之后再卖出一次。你最多完成 k 笔交易。手里最多持有一股：再次买入前，必须先卖掉手上的股票。
返回能获得的最大利润。
示例 1
输入：k = 2, prices = [2,4,1] 输出：2
解释：第 1 天以 2 买入，第 2 天以 4 卖出，赚 2。
示例 2
输入：k = 2, prices = [3,2,6,5,0,3] 输出：7
解释：第 2 天以 2 买、第 3 天以 6 卖赚 4；第 5 天以 0 买、第 6 天以 3 卖赚 3，共 7。
数据范围
1 <= k <= 1001 <= prices.length <= 10000 <= prices[i] <= 1000
解题思路
每天结束时，按“已经发起了几笔交易、手里有没有股票”划分状态。buy[j] 表示已进行第 j 次买入且持股时的最大余额，sell[j] 表示已完成 j 笔交易、空仓时的最大余额。今天的 buy[j] 要么保持，要么由 sell[j-1] 花 p 买入；sell[j] 要么保持，要么把 buy[j] 以 p 卖出。按天滚动更新即可。
为什么正确
处理完第 t 天后，buy[j] 和 sell[j] 是前 t 天里对应状态能达到的最大余额。
复杂度分析
时间 O(nk)，空间 O(k)。
易错点
buy 的初值不能是 0，否则相当于“免费持股”；另外第 j 次买入只能接在 sell[j-1] 后面，不能接在 sell[j] 后面。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
buy = [-math.inf] * (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]class Solution {
public int maxProfit(int k, int[] prices) {
int[] buy = new int[k + 1];
Arrays.fill(buy, Integer.MIN_VALUE / 2);
int[] sell = new int[k + 1];
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];
}
}class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
vector<int> buy(k + 1, INT_MIN / 2);
vector<int> 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];
}
};func maxProfit(k int, prices []int) int {
buy := make([]int, k+1)
for j := range buy {
buy[j] = math.MinInt32 / 2
}
sell := make([]int, k+1)
for _, p := range prices {
for 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]
}var maxProfit = function(k, prices) {
const buy = new Array(k + 1).fill(-Infinity);
const sell = new Array(k + 1).fill(0);
for (const p of prices) {
for (let 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];
};function maxProfit(k: number, prices: number[]): number {
const buy: number[] = new Array(k + 1).fill(-Infinity);
const sell: number[] = new Array(k + 1).fill(0);
for (const p of prices) {
for (let 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];
}