class Solution {
    
    // key = (i, buying), value = max profilt
    Map<String, Integer> dp = new HashMap<>();
    int[] prices;

    // 주식을 여러개 살 수 없고, 주식을 매도한 다음날 살 수 없다.
    // T: O(n)
    public int maxProfit(int[] prices) {
        this.prices = prices;
        return dfs(0, true);
    }

    // State: Buying or Selling
    // If Buy  -> i + 1
    // If Sell -> i + 2 (cooldonw one day)
    public int dfs(int i, boolean buying) {
        // Base case
        if (i >= prices.length) {
            return 0;
        }

        String key = i + "-" + buying;

        if (dp.containsKey(key)) {
            return dp.get(key);
        }

        int profit = Integer.MIN_VALUE;
        if (buying) {
            profit = dfs(i + 1, !buying) - prices[i];
        } else {
            profit = dfs(i + 2, !buying) + prices[i];
        }

        int cooldown = dfs(i + 1, buying);
        dp.put(key, Math.max(profit, cooldown));

        return dp.get(key);
    }
}