123. Best Time to Buy and Sell Stock III

Use 4 variables to keep the maximum profits:

1. hold1: maximum profit if we buy the first stock.
2. release1: maximum profit if we sell the first stock, i.e., we complete 1 transaction.
3. hold2: maximum profit if we buy the second stock.
4. release2: maximum profit if we sell the second stock, i.e., we complete 2 transactions.

The dependency is hold1 -> release1 -> hold2 -> release2

1:  class Solution {  
2:  public:  
3:    int maxProfit(vector<int>& prices) {  
4:      int hold1 = INT_MIN, hold2 = INT_MIN;  
5:      int release1 = 0, release2 = 0;  
6:      for (int i = 0; i < prices.size(); i++) {  
7:        hold1 = max(hold1, -prices[i]);  
8:        release1 = max(release1, hold1 + prices[i]);  
9:        hold2 = max(hold2, release1 - prices[i]);  
10:        release2 = max(release2, hold2 + prices[i]);  
11:      }  
12:      return release2;  
13:    }  
14:  };