Leetcode 123. Best Time to Buy and Sell Stock III

Type: dynamic programming （Sequence type)
Approach:
1. 5 phases in total:
  - Phase 1: No stock
  - Phase 2: Holding One stock (first)
  - Phase 3: No stock and seld one stock
  - Phase 4: Holding one stock (second)
  - Phase 5: No stock and seld two stocks
2. DP state transfer equation:
  - dp[i][j]: In first ith day of phase j maximum profits
  - For phase 1,3,5:
    1. The phase of first i-1 is the same as first i', which means we still don't have any stock:
      - tmp1 = dp[i-1][j]
    2. The phase of first i-1 is different from first i', which means we sell the stock in the i-1's day:
      - tmp2 = dp[i-1][j-1]+price[i-1]-price[i-2]
    3. dp[i][j] = max(tmp1, tmp2)
  - For phase 2, 4:
    1. The phase of first i-1 is different from first i', which means that we just buy a stock on day i-1:
      - tmp1 = dp[i-1][j-1]
    2. Otherwise:
      - tmp2 = dp[i-1][j]+price[i-1]-price[i-2]
    3. dp[i][j] = max(tmp1, tmp2)
3. Boundary and results:
  - Init: dp[i][j] = -float('inf'); dp[0][1] = 0
  - Result: maximum of dp[-1][1], dp[-1][3], dp[-1][5]
4. Complexity:
  - Time: O(n*5)
  - Space: O(n)