想法 #

在股票交易中，寻找在最多 k 次交易中获得最大利润的问题可以通过逐步考虑每一步的交易来分解。初步想法是使用动态规划来管理买入和卖出股票的不同状态。

方法 #

这个方法的核心思想是维护两个表：buy 和 sell。buy[i][j] 表示在进行 i 次交易后的第 j 天的最大利润，而 sell[i][j] 表示在进行 i 次交易后的第 j 天卖出后的最大利润。 更新这些表的公式为：

• 买入：

  $buy[i][j] = max(buy[i][j-1], sell[i-1][j] - prices[j-1])$

  这意味着第 j 天进行第 i 次买入后的最大利润是

  1. **当天不买入：**已经持有股票了（buy数组）的最大利润。
  2. **当天买入：**是没持有股票的时候（sell数组）的最大利润减去当天的买入价格。

• 卖出：

  $sell[i][j] = max(sell[i][j-1], buy[i][j] + prices[j-1])$

  这意味着第 j 天进行第 i 次卖出后的最大利润是

  1. **当天不卖出：**前一天的最大利润
  2. **今天卖出：**最好的持仓利润加上当天的卖出价格。

示例 #

prices = [3, 2, 6, 5, 0, 3]
k = 2
Day     |  Day 0  |  Day 1  |  Day 2  |  Day 3  |  Day 4  |  Day 5  |  Day 6
----------------------------------------------------------------------
buy[0]  | -100001 | -100001 | -100001 | -100001 | -100001 | -100001 | -100001
sell[0] |    0    |    0    |    0    |    0    |    0    |    0    |    0
----------------------------------------------------------------------
buy[1]  | -100001 |   -3    |   -2    |   -2    |   -2    |    0    |    0
sell[1] |    0    |    0    |    0    |    4    |    4    |    4    |    4
----------------------------------------------------------------------
buy[2]  | -100001 |   -3    |   -2    |   -2    |   -1    |    4    |    4
sell[2] |    0    |    0    |    0    |    4    |    4    |    4    |    7
----------------------------------------------------------------------

初始化（第0天）：

• buy[0] 和 sell[0]： 这些初始化用于提供计算的基线：
  • buy[0][*] 设置为 100001，表示没有发生买入。
  • sell[0][*] 设置为 0，因为还没有发生卖出。 迭代1（第一次交易）：
• 第1天：
  • buy[1][1] = -3： 第一天买入的价格为 3，因此 buy[1][1] = -3。这反映了潜在的利润（因为还没有卖出，所以是负的）。
  • sell[1][1] = 0： 因为我们不能在买入当天卖出，卖出的最大利润仍然为 0。
• 第2天：
  • buy[1][2] = -2： 第2天的价格为 2，低于第1天。因此，第2天买入更有利，将 buy[1][2] = -2。
  • sell[1][2] = 0： 因为还没有卖出，利润仍然为 0。
• 第3天：
  • buy[1][3] = -2： 尽管第3天的价格是 6，但持有第2天以 2 买入的股票仍然是最好的选择。因此，buy[1][3] = -2 保持不变。
  • sell[1][3] = 4： 如果我们以 6 的价格卖出第2天买入的股票，利润为 4，因此 sell[1][3] = 4。
• 第4天：
  • buy[1][4] = -2： 第4天价格降至 5，继续持有第2天的仓位（buy[1][4] = -2）比以更高价格买入要好。
  • sell[1][4] = 4： 如果不在第4天卖出，利润仍然为 4。
• 第5天：
  • buy[1][5] = 0： 价格降至 0，这是最好的买入时机。但是，由于这仍然是第一次交易的一部分，当天的最大潜在损失为 0，更新为 buy[1][5] = 0。
  • sell[1][5] = 4： 第一次交易的最大利润仍然为 4，如果没有卖出。
• 第6天：
  • buy[1][6] = 0： 买入决策保持与第5天相同，没有进一步的交易发生在这一迭代中。
  • sell[1][6] = 4： 第一次交易的最大利润仍然为 4，因为没有找到更好的卖出价格。 迭代2（第二次交易）：
• 第1天：
  • buy[2][1] = -3： 如果在第1天进行了第二次交易的买入，潜在损失为 3。
  • sell[2][1] = 0： 由于没有发生卖出，利润仍然为 0。
• 第2天：
  • buy[2][2] = -2： 第2天最好的行动是以 2 的价格买入，因此 buy[2][2] = -2。
  • sell[2][2] = 0： 由于还没有卖出，利润仍然为 0。
• 第3天：
  • buy[2][3] = -2： 持有第2天的仓位仍然是最好的选择，因此 buy[2][3] = -2。
  • sell[2][3] = 4： 在第3天以 6 的价格卖出，获得的利润与第一次交易相同，因此 sell[2][3] = 4。
• 第4天：
  • buy[2][4] = -1： 第4天，在完成第一次卖出后，第二次交易最好的选择是以 5 的价格买入，因此 buy[2][4] = -1。
  • sell[2][4] = 4： 如果没有卖出，利润仍然为 4。
• 第5天：
  • buy[2][5] = 4： 价格降至 0，这是在第一次卖出后的最佳买入时机，更新为 buy[2][5] = 4。这带来了第一次交易的利润。
  • sell[2][5] = 4： 没有发生卖出，因此利润仍然为 4。
• 第6天：
  • buy[2][6] = 4： 第5天的买入决策仍然有效，因为没有更好的机会出现。
  • sell[2][6] = 7： 最后，在第6天以 3 的价格卖出，第二次交易的最大利润为 7。

最终结果： #

• 完成两次迭代后，最多进行 2 次交易所能获得的最大利润为 7。这是在 sell[2][6] 中找到的结果。

复杂度 #

• 时间复杂度:

  该解决方案的时间复杂度为 $O(k \times n)$，因为我们遍历了交易次数 k 和天数 n。

• 空间复杂度:

  空间复杂度为 $O(k \times n)$，因为我们为 buy 和 sell 维护了二维数组。

代码 #

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> buy(k+1,vector<int>(n+1,-100001));
        vector<vector<int>> sell(k+1,vector<int>(n+1,0));
        for(int i = 1;i<=k;i++){
            for(int j = 1;j<=n;j++){
                buy[i][j] = max(buy[i][j-1],sell[i-1][j] - prices[j-1]);
                sell[i][j] = max(sell[i][j-1],buy[i][j]+prices[j-1]);
            }
        }
        return sell[k][n];
    }
};

空间复杂度改进 #

为了优化空间复杂度，我们可以注意到第 i 次交易仅依赖于上一次交易的结果。这使得我们可以将 buy 和 sell 表从二维数组减少为一维数组。通过这样做，空间复杂度从$ O(k×n)$改善为 $O(n)$。 以下是优化后的代码：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<int> buy(n+1,-100001);
        vector<int> sell(n+1,0);
        for(int i = 1;i<=k;i++){
            for(int j = 1;j<=n;j++){
                buy[j] = max(buy[j-1],sell[j] - prices[j-1]);
                sell[j] = max(sell[j-1],buy[j]+prices[j-1]);
            }
        }
        return sell[n];
    }
};