class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        // Do nothing, firstBuy, firstSell, secondBuy, secondSell, ...
        vector<int> dp(2 * k + 1);

        for(int i = 1; i < 2 * k + 1; i += 2) {
            dp[i] = -prices[0];
        }

        for(int i = 1; i < prices.size(); i++) {
            for(int j = 1; j < 2 * k + 1; j++) {
                if(j % 2 == 1) {
                    // buy score
                    // last day sell score - today stock price
                    dp[j] = max(dp[j], dp[j-1] - prices[i]);
                } else {
                    // sell score
                    // today stock price + last day buy score
                    dp[j] = max(dp[j], prices[i] + dp[j-1]);
                }
            }
        }

        return dp[2 * k];
    }
};