两次买卖股票

Question

我正在努力理解这个问题，当我最多可以买卖股票两次时，我需要找出最大利润。提供的解决方案谈到从左到右维护价格差异数组，这对我来说很有意义。然而，该帖子还谈到了从右到左维护另一组价格差异，我无法理解这种逻辑为什么在第一次交易后会产生利润。

Prices= [1, 4, 5, 7, 6, 3, 2, 9]
left  = [0, 3, 4, 6, 6, 6, 6, 8]
right = [8, 7, 7, 7, 7, 7, 7, 0]
max_profit = 13

Answer 1

您提到的建议解决方案中有两个数组这一事实与仅允许使用 2 个事务的问题的约束有关。

正如还规定的那样，事务不应该被插入——即一个事务应该在另一个事务之前（在左边）（在右边）。

更具体地说，提议的解决方案中的两个数组表示如下：

• left[i] = 在区间 [0, i] 内买入和卖出的最佳交易。如果在时间 j 完成卖出（j 在 [0, i] 中），则买入应以 0 到 j 的最低价格完成。

• right[i] = 在区间 [i, n-1] 内可以通过买卖进行的最佳交易。如果买入是在时间 j（j 在 [i, n-1] 中），卖出应该以从 j 到 n-1 的最高价格进行。

需要找到的只是两个事务的一个很好的分离点i。那么最佳组合将涉及利润 left[i] + right[i]，这可以通过尝试所有可能的i值来找到。