123. Best Time to Buy and Sell Stock III

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int mx = prices[n - 1];
        int profit[n];
        profit[n - 1] = 0;
        for(int i = n - 2; i >= 0; i--) {
            mx = max(mx, prices[i]);
            profit[i] = max(profit[i + 1], mx - prices[i]);
        }
        int mn = prices[0];
        int ans = profit[0];
        profit[0] = 0;
        for(int i = 1; i < n; i++) {
            mn = min(mn, prices[i]);
            ans = max(ans, profit[i] + profit[i - 1]);
            profit[i] = max(profit[i - 1], prices[i] - mn);
        }
        return ans;
    }
};