参考的leetcode#123。但是感觉leetcode的O(1)的解法思路有点反人类，就稍微转换了一下。
先看(四)的解法再看三(因为四不用空间优化, 好理解)。

举例
price: 3  16  6  14  10  19

大致可以理解为把#买卖股票的最好时机(一)#走三遍。

第一遍
和#买卖股票的最好时机(一)#一模一样，记录当前最低价minP。
C1就是1次买卖结束后你手上最多可能有的现金
C1[i] = max(P[j]-minP[j]), for all j<=i
price: 3  16  6  14  10  19
minP:  3  3   3  3   3   3
c1:    0  13  13 13  13  16

第二遍
C2[i]理解为你选择在<=i天第二次买入股票后手上能有的最多的现金
第一次的利润C1，减去第二次买入的股价，取最优(i.e. max):
C2[i] = max(C1[j]-P[j]), for all j<=i
price: 3  16  6  14  10  19
c1:    0  13  13 13  13  16
c2:   -3  -3  7  7   7   7
这个例子里选择在股价为6时第二次买出最优 13-6=7
Ok, 现在你手上有c2的现金和1股。

第三遍
C3[i]就是你最后再把那1股卖掉后你手上能有的最多的现金，也就是这题的解
就是第二次买完能剩的现金C2，加上第二次卖出的股价, 取最优(i.e. max):
C3[i] = max(C2[j] + P[j]), for all j<=i
price: 3  16  6  14  10  19
c1:    0  13  13 13  13  16
c2:   -3  -3  7  7   7   7
c3:    0  13  13 21  21  26
还原一下操作，就是3块买，16卖，6买，19卖。总营收26

这个缕清了之后就是优化记忆。
对于每个i, DP只需要记录之前的C1,C2,C3的max，(当然还有minP).

时间O(n)
空间O(1)

import java.util.*;

public class Solution {
    public int maxProfit (int[] prices) {
      if (prices.length <= 1) return 0;
      
      // 定义 
      //   C1[i]: max profit at day i, with at most 1 buy/sell on or before day i
      //     = Max( Prices[i] - Min{ Prices[j], for all j <= i } )
      //   C2[i]: max cash after buying again on or before day i
      //     = Max{ C1[j] - Price[j], for all j <= i }
      //   C3[i]: max cash after selling again on or before day i
      //     = Max{ C2[j] + Price[j], for all j <= i }
      
      int minP1 = prices[0]; // 目前已知的最低价
      int c1 = 0;
      int c2 = c1-prices[0];
      int c3 = 0; // c2 + price[0] = c1 + price[0] - price[0] = 0
      
      for (int i = 1; i < prices.length; i++) {
        minP1 = Math.min(minP1, prices[i]);
        c1 = Math.max(c1, prices[i] - minP1);
        c2 = Math.max(c2, c1 - prices[i]);
        c3 = Math.max(c3, c2 + prices[i]);
      }
      
      return Math.max(0, c3);
    }
}