class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(4));

        for(int i = 0; i < n; i++) {
            dp[i][0] = -prices[0];
        }

        for(int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i-1][0], max(dp[i-1][1] - prices[i], dp[i-1][3] - prices[i]));
            dp[i][1] = max(dp[i-1][3], dp[i-1][1]);
            dp[i][2] = dp[i-1][0] + prices[i];
            dp[i][3] = dp[i-1][2];
        }

        return max(dp[n-1][1], max(dp[n-1][2], dp[n-1][3]));
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> dp(4);
        dp[0] = -prices[0];

        for(int i = 1; i < n; i++) {
            int temp = dp[0];
            int temp2 = dp[2];

            dp[0] = max(dp[0], max(dp[1] - prices[i], dp[3] - prices[i]));
            dp[1] = max(dp[3], dp[1]);
            dp[2] = temp + prices[i];
            dp[3] = temp2;
        }

        return max(dp[1], max(dp[2], dp[3]));
    }
};