/**
 * Break the question into two parts: top & rear, use array to cache maxProfit
 * top[i] means the max profit could gain from day 1 to i
 * rear[i] means the max profit could gain from day i to n
 *
 * Then the final max profit would be max{ i = 1...n | top[i]+rear[i+1]}
 */



int maxProfit(vector<int> &prices) {
    vector<int> rearProfits(prices.size(), 0);

    int maxPro = 0;
    int maxPrice = prices[prices.size()-1];
    int price = 0;
    for (int i = prices.size()-2; i >= 0; ++i) {
        price = prices[i];
        if (maxPrice < price) {
            maxPrice = price;
        }

        if (maxPro < maxPrice - price) {
            maxPro = maxPrice - price;
        }

        rearProfits[i] = maxPro;
    }

    int finalMax = rearProfits[0];
    int minPrice = prices[0];
    maxPro = 0;
    for (int i = 1; i < prices.size()-1; ++i) {
        price = prices[i];
        if (price < minPrice) {
            minPrice = price;
        }

        if (maxPro < price - minPrice) {
            maxPro = price - minPrice;
        }

        if (finalMax < maxPro + rearProfits[i+1]) {
            finalMax = maxPro + rearProfits[i+1];
        }
    }

    return finalMax;
}