123. Best Time to Buy and Sell Stock III

Description

Say you have an array for which theithelement is the price of a given stock on dayi.

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

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Discussion

Method

DP Kadane's Algorithm

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        /*
        construct left most array
        construct right most array

        get max profit based on above arrays
        */
        int rst = 0;
        vector<int> leftMost(prices.size(), 0);
        vector<int> rightMost(prices.size(), 0);
        int extTmp = INT_MAX;
        for(int loop = 1; loop < prices.size(); ++loop) {
            extTmp = min(extTmp, prices[loop - 1]);
            leftMost[loop] = max(prices[loop] - extTmp, leftMost[loop - 1]);
        }

        extTmp = INT_MIN;
        for(int loop = prices.size() - 1; loop >= 0; --loop) {
            if(loop == prices.size() - 1) {
                rightMost[loop] = 0;
                continue;
            }
            extTmp = max(extTmp, prices[loop + 1]);
            //rightMost[loop] = prices[loop + 1] - prices[loop];
            rightMost[loop] = max(extTmp - prices[loop], rightMost[loop + 1]);
        }

        copy(leftMost.begin(), leftMost.end(), ostream_iterator<int>(cout, ","));
        cout << endl;
        copy(rightMost.begin(), rightMost.end(), ostream_iterator<int>(cout, ","));
        cout << endl;

        for(int loop = 0; loop < prices.size(); ++loop) {
            int left = (loop == 0)? 0 : leftMost[loop];
            int right = (loop == prices.size() - 1) ? 0 : rightMost[loop];
            rst = max(rst, left + right);
        }
        return rst;
    }
};