120. 买卖股票的最佳时机 IV
题目
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
思路:动态规划状态机(推广到k词交易)
推广到 k 笔交易，我们就需要 2k 个变量（或者两个长度为 k+1 的数组）： - buy[j]：进行第 j 次买入后（即持有股票，且已经完成了 j-1 笔交易）的最大利润 - sell[j]：完成第 j 笔交易后（即不持有股票）的最大利润 其中 j 从 1 到 k。注意：buy[0] 和 sell[0] 表示未进行任何交易，利润为 0。
状态转移
遍历每一天的价格 p，对于每个交易次数 j（从 1 到 k），我们更新： 第 j 次买入：要么保持之前的买入，要么今天买入（基于上一次卖出后的利润减去今天的价格） 纯文本 buy[j] = max(buy[j], sell[j-1] - p) 第 j 次卖出：要么保持之前的卖出，要么今天卖出（基于本次买入后的利润加上今天的价格） 纯文本 sell[j] = max(sell[j], buy[j] + p) 注意更新顺序：先更新 buy[j]，再更新 sell[j]，因为 sell[j] 要用到当天更新后的 buy[j]（即考虑了今天买入的情况）。实际上，由于一天内可以先卖后买（如果之前持有股票），但这里我们允许同一天既卖又买（相当于不持仓），所以顺序没问题。
初始化 buy[j] 初始化为 -∞（表示尚未进行第 j 次买入），或者初始化为 -prices[0] 但需要小心。更安全的做法：将所有 buy[j] 初始化为 Integer.MIN_VALUE，sell[j] 初始化为 0。 遍历第一天时，我们手动设置 buy[1] = -prices[0]，然后从第二天开始正常更新。 或者更通用的初始化：
对于第一天，只可能进行第一次买入，所以： buy[1] = -prices[0] 其他 buy[j] 保持 -∞（或一个极小值） 所有 sell[j] = 0 然后在后续遍历中，通过状态转移自然更新。
特殊情况：k 很大时
如果 k >= n/2（n 是天数），那么相当于可以进行无限次交易（因为一次交易至少需要两天）。此时可以用贪心法：只要今天价格比昨天高，就累加差价。这样能更快得到答案，也避免了大量无意义的 DP 计算。
class Solution {
fun maxProfit(k: Int, prices: IntArray): Int {
val n = prices.size
if (n == 0 || k == 0) return 0
// 如果 k 很大，相当于无限次交易，用贪心
if (k >= n / 2) {
var profit = 0
for (i in 1 until n) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1]
}
}
return profit
}
// buy[j] 表示第 j 次买入后的最大利润
// sell[j] 表示第 j 次卖出后的最大利润
val buy = IntArray(k + 1) { Int.MIN_VALUE }
val sell = IntArray(k + 1) { 0 }
for (price in prices) {
for (j in 1..k) {
buy[j] = maxOf(buy[j], sell[j - 1] - price)
sell[j] = maxOf(sell[j], buy[j] + price)
}
}
return sell[k]
}
}
复杂度
- 时间复杂度: O(n × k)需要遍历 n 天，每天内层循环 k 次。但当 k ≥ n/2 时，我们用贪心 O(n) 代替。
- 空间复杂度: O(k)
- 邮箱 ：charon.chui@gmail.com
- Good Luck!