123. Best Time to Buy and Sell Stock III

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

class Solution {
public:
    int maxProfit(vector<int>& p) {
        vector<int> dp(p.size());
        int mi = p[0], ma = p.back(), n = p.size(), res = 0;
        for(int i = 1; i < n; i++) {
            dp[i] = max(p[i] - mi, dp[i-1]);
            mi = min(mi, p[i]);
        }
        res = dp.back();
        for(int i = n - 2; i > 0; i--) {
            res = max({res, dp[i-1] + ma - p[i], dp[i]});
            ma = max(ma, p[i]);
        }
        return res;
    }
};