Best Time to Buy and Sell Stock III

Say you have an array for which the ith 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.

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

[Analysis]

Based on Best Time to Buy and Sell Stock II, I first tried the naive approach to divide the prices in two half, and try to find the max of the sum of the two halves. This works on small test cases but failed on larger ones. Indeed, the complexity was .

We can actually do this in O(n). The idea is to scan through the prices forward, and find the maxProfit for day i if we sell on or before day i. We store these in an array (DP). Then, we scan backward and do the same thing. That is, we try to find the maxProfit if we buy on, or after day i.

We just need to find the max sum based on these two arrays. Turns out, we don’t even need to keep the backward one, just the maxProfit will do.

Both scanning cost O(n) so this would be a O(n) in the end.

This solution reminds me of Candy. It seems that these kind of problems which involve solving the same issue from both side can always be solved by scanning forward and scanning backward. Don’t try to do solve these problems in one pass, rather, go forward and backward and solve half of the problem. The big O will give you the same complexity as only one scanning. So the backward scanning is “free”.

class Solution {

    void maxProfitHelper(const vector<int> &prices, vector<int> &maxEndWith) {
        int lowest = prices[0];
        int maxProfit = 0;

        for (int i = 0; i<prices.size(); ++i){

            if (prices[i] < lowest) {
                lowest = prices[i];
            }

            if (prices[i]-lowest > maxProfit){
                maxProfit = prices[i] - lowest;
            }

            maxEndWith.push_back(maxProfit);
        }
    }

public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty()) return 0;

        vector<int> maxEndWith;
        maxProfitHelper(prices, maxEndWith);

        int res = maxEndWith.back();

        int highest = prices.back();
        int maxProfit = 0;

        for (int i=prices.size()-2; i>=0; --i) {
            if (highest - prices[i] > maxProfit)
                maxProfit = highest - prices[i];

            if (prices[i] > highest)
                highest = prices[i];

            if (maxEndWith[i]+maxProfit > res)
                res = maxEndWith[i]+maxProfit;
        }

        return res;
    }
};