https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

    • 只能做两次交易

    image.png

    随便拿两个上坡可能不是最优的结果

    我一定要在i位置的时候，两次交易做完，并且最后一次交易的卖出时机在i位置

    image.png
    圆圈部分表示做完一次交易后并且减去一个买入价格的最优值，
    也就是第二次的本钱提前减掉了
    而且我要的是整体的最优，也就是他俩减完的最优
    举个例子
    image.png

    来看不最优的例子
    image.png

    好了，那么来到i位置时就直接把i的值加到之前的信息就是两次交易的最优值了

    接下来就是看这个信息怎么求了
    初始化0位置 = -prices[0]

    比如我是i位置，即将进入i+1位置，那么我怎么更新我的这个信息去给i+1用呢？

    两种情况
    1）第二次交易的买入时机不在i位置
    那么0~i-1的最优就是0~i的最优
    2）第二次交易的买入时机一定要在i位置
    之前第一次交易的最优 - [ i ]
    image.png

    1.  public int maxProfit(int[] prices) {
    2.      int firstMax = 0;
    3.      int firstMaxMinusBuy_Max = -prices[0];
    4.      int ans = 0;
    5.      int min = prices[0];
    6.      for (int i = 1; i < prices.length; i++) {
    7.          ans = Math.max(ans, firstMaxMinusBuy_Max + prices[i]);
    8.          min = Math.min(min, prices[i]);
    9.          firstMax = Math.max(firstMax, prices[i] - min);
    10.          firstMaxMinusBuy_Max = Math.max(firstMaxMinusBuy_Max, firstMax - prices[i]);
    11.      }
    12.      return ans;
    13.  }