88. 买卖股票的最佳时机 IV - Kotlin 动态规划

原题地址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/

题解

买入和卖出实际上是一系列顺序固定的连续操作：

• 第0次卖出（第二次操作）必然在第0次买入（第一次操作）之后
• 第1次买入（第三次操作）必然在第0次卖出（第二次操作）之后
• …

dp[i][j]记录第i天的第j次操作能够获得的最大利润，可以知道

• 当j为偶数时，必定为买入操作（0、2、4、6、8，…）
  • 此时第j次操作的最大利润=第j-1次操作的最大利润-prices[i]
• 当j为奇数时，必然为卖出操作（1，3，5，7，9，…）
  • 此时第j次操作的最大利润=第j-1次操作的最大利润+prices[i]

我们用一个max数组维护每一步操作的最大利润，每次遍历第j步操作时，其最大利润即第j-1步的最大利润+/-当天的股价即可

最后输出max数组中的最大值即可

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    fun maxProfit(k: Int, prices: IntArray): Int {
        val dp = Array(prices.size) { IntArray(k * 2) { 0 } }
        val max = IntArray(k * 2) { i -> if (i % 2 == 0) Int.MIN_VALUE else 0 }
        for (i in prices.indices) {
            for (trade in 0 until Math.min(i+1,dp[i].size)) {
                dp[i][trade] =
                    if (trade % 2 == 0)
                        (if (trade > 0) max[trade - 1] else 0) - prices[i]
                    else
                        max[trade - 1] + prices[i]
                max[trade] = Math.max(max[trade], dp[i][trade])
            }
        }
        return max.max()!!
    }
}