1. 题目描述

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

  1. 输入：k = 2, prices = [2,4,1]
  2. 输出：2
  3. 解释：在第 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 。


提示：

  • 0 <= k <= 100
  • 0 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

    2. 解题思路

    在题目121《买卖股票的最佳时机》中，我们只能进行一次买入卖出，在题目123《买卖股票的最佳时机 III》中，我们可以进行两次买入卖出操作。而在这道题目中，我们可以进行k次买入卖出操作。这里我们也可以使用动态规划来解答。

每次我们只能进行[1, k]次中的某次交易或不交易，所以可能有2k+1中状态：

  • 无操作，一直没有买
  • dp[0]：到最后只买了一笔，未卖出
  • dp[1]：到最后只卖了一笔，并卖出
  • dp[2]：到最后买了两笔，只卖出一笔
  • dp[3]：到最后买了两笔，两笔都卖出
  • dp[4]：到最后买了三笔，只卖出两笔
  • ······

我们可以枚举一天的所有可能，取现金最大值：

  • 不交易，现金 不变
  • 进行[1, k]的某次交易
    • 买入，现金 -= 当天股票价格
    • 卖出，现金 += 当天股票价格

复杂度分析

  • 时间复杂度：O(n * min(n, k))，其中 n 是数组 prices 的长度，即使用二重循环进行动态规划需要的时间。

  • 空间复杂度：O(min(n,k))。

    3. 代码实现

    ```javascript /**

    • @param {number} k
    • @param {number[]} prices

    • @return {number} / var maxProfit = function(k, prices) { const dp = new Int16Array(k 2).fill(-prices[0])

      for (let i = 0; i < prices.length; i++) {

      for (let j = 0; j < dp.length; j++) 
    {
        dp[j] = Math.max(dp[j], (dp[j - 1] || 0) + (j & 1 ? prices[i] : -prices[i]))
    }

      } return Math.max(0, …dp) };

```

4. 提交结果

image.png