想法

方法

• 买入：
这意味着第 j 天进行第 i 次买入后的最大利润是
1. 当天不买入：已经持有股票了（buy数组）的最大利润。
2. 当天买入：是没持有股票的时候（sell数组）的最大利润减去当天的买入价格。

• 卖出：
这意味着第 j 天进行第 i 次卖出后的最大利润是
1. 当天不卖出：前一天的最大利润
2. 今天卖出：最好的持仓利润加上当天的卖出价格。

示例

• buy[0] 和 sell[0]： 这些初始化用于提供计算的基线：
• buy[0][*] 设置为 100001，表示没有发生买入。
• sell[0][*] 设置为 0，因为还没有发生卖出。

• 第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，因为没有找到更好的卖出价格。

• 第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] 中找到的结果。

复杂度

• 时间复杂度:
该解决方案的时间复杂度为 ，因为我们遍历了交易次数 k 和天数 n。

• 空间复杂度:
空间复杂度为 ，因为我们为 buy 和 sell 维护了二维数组。

代码

空间复杂度改进