123 Best Time to Buy and Sell Stock III

Say you have an array for which the $$i_{th}$$ element is the price of a given stock on day $$i$$.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Solution

class Solution {
  public:
    int maxProfit(vector<int> &prices) {
        int n = prices.size();
        if ( n == 0 ) return 0;
        // don't-1, don't -2, do-1, do-2
        vector<int> result(4, 0), tmp(4, 0);
        for ( int i = 1; i <= n-1; i++ ) {
            // don't - 1
            tmp[0] = max(result[0], result[2]);
            // don't - 2
            tmp[1] = max(result[1], result[3]);
            // do - 1
            tmp[2] = max(0, result[2]) + prices[i] - prices[i-1];
            // do - 2
            tmp[3] = max(result[0], result[3]) + prices[i] - prices[i-1];
            result.swap(tmp);
        }
        int maxP = 0;
        for ( int i = 0; i <= 3; i++ ) {
            maxP = max(maxP, result[i]);
        }
        return maxP;
    }
};