买卖股票的最佳时机三

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 输入: [3,3,5,0,0,3,1,4] 输出: 6 解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。 示例 2: 输入: [1,2,3,4 《买卖股票的最佳时机三》 在股票投资领域，如何把握最佳买卖时机是每个投资者关注的焦点。本问题探讨的是在给定的股票价格数组中，如何通过最多两次交易获得最大利润。具体而言，给定一个数组`prices`，其中`prices[i]`表示第`i`天股票的价格，目标是设计一个算法，计算在最多进行两次交易的情况下，所能获取的最大利润。 我们需要明确规则：每次交易完成后，你不能同时持有股票（即你必须在再次购买前卖出股票）。这限制了我们不能进行连续的买入和卖出操作。下面我们将分析两种不同的解决方案。 **解法一：双指针法** 该方法的核心是维护两个数组，`left`和`right`。`left`数组记录到当前位置为止，所能获得的最大利润，而`right`数组记录从当前位置到最后一天，所能获得的最大利润。首先初始化`left`数组，对于每个位置`i`，`left[i]`取`left[i-1]`和`prices[i] - min_value`中的较大值，其中`min_value`是到目前为止的最低价格。接着，从后往前遍历数组计算`right`数组，`right[i]`取`right[i+1]`和`max_value - prices[i]`中的较大值，其中`max_value`是到目前为止的最高价格。遍历`left`和`right`数组，找到最大的两次利润之和。 **解法二：动态规划** 另一种解法是使用动态规划的思想，定义四个状态：没有购买股票、持有股票但未卖出、已卖出一次股票和已卖出两次股票。对于每一天，我们都更新这四个状态下的最大利润。初始时，未购买股票的状态利润为0，持有股票的利润为负（因为持有股票意味着有成本），卖出一次和卖出两次的利润也初始化为0。然后，对于每一天，根据当前价格更新这些状态，取最大值。 在实际实现中，可以通过优化简化这个过程。注意到在没有购买股票的状态下，利润始终为0，因此可以省略这个状态。只需考虑持有股票、卖出一次和卖出两次的状态，初始时持有股票的利润为负，其他两种状态为0。然后，每天更新这三个状态，取最大值。 例如，对于输入`[3,3,5,0,0,3,1,4]`，解法一和解法二都会得出最大利润为6。在第4天买入，第6天卖出得到3利润；然后在第7天再次买入，第8天卖出，又得到3利润。 总结来说，解决此类问题的关键在于理解交易的限制条件并合理利用数据结构（如动态规划或双指针）来有效地遍历和更新状态。通过这两个解法，我们可以高效地找出在给定条件下，最多两次交易所能获得的最大利润。在实际股票投资中，这样的策略虽然简单，但却能提供对市场动态的一种基本理解，帮助投资者做出更为理性的决策。