Best Time to Buy and Sell Stocks III -- Leetcode

[Question]
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]
It is equivalent to make a partition on the given array, and get the best sum of max profit from each of the two sections. Scanning from left to right, we can get the best profit for buying-and-selling the stock between day 0-th and day i-th. Scanning from the right to left, we can get the best profit for buying-and-selling the stock between day i-th and last day. Add two "best profit" at day i-th, and find out the maximum -- that is the maximum profit we can get if two transactions are allowed.

O(N).

[Solution]


class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty() || prices.size()==1) return 0;

        vector<int> left_profit (prices.size(), 0);
        vector<int> right_profit(prices.size(), 0);
        int high=0, low=0;
   
        low = prices[0];
        for (int i=1; i< prices.size(); i++) {
            low = min(low, prices[i]);
            left_profit[i] = max( prices[i]-low, left_profit[i-1] );
        }
   
        high = prices.back();
        for (int i=prices.size()-2; i>=0; i--) {
            high = max(high, prices[i]);
            right_profit[i] = max( high - prices[i],  right_profit[i+1] );
        }
   
        int max_profit=0;
        for (int i=0; i< prices.size(); i++) {
            int sum = left_profit[i] + right_profit[i];
            max_profit = max(sum, max_profit);
        }
       
        return max_profit;
    }
};