Best Time to Buy and Sell Stock III.txt

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (prices.size() < 2)
            return 0;
        int size = prices.size(), l[size], r[size];
        int miv = prices[0], mav = prices.back();
        l[0] = 0;
        for (int i = 1; i < size; i++) {
            miv = min(miv, prices[i]);
            l[i] = max(l[i-1], prices[i] - miv);
        }
        r[size-1] = 0;
        for (int i = size - 2; i >= 0; i--) {
            mav = max(mav, prices[i]);
            r[i] = max(r[i+1], mav - prices[i]);
        }
        int ret = r[0];
        for (int i = 0; i < size - 1; i++)
            ret = max(ret, l[i] + r[i+1]);
        return ret;
    }
};