class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int dp[] = new int[n+1];
        dp[1] = nums[0];
        for(int i = 2;i <=n;i++){
            dp[i] = Math.max(dp[i-1],(dp[i-2]+nums[i-1]));
        }
        return dp[n];
    }
}

class Solution {
    HashMap<TreeNode,Integer> f = new HashMap<>();
    HashMap<TreeNode,Integer> g = new HashMap<>();
    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root,0),g.getOrDefault(root,0));
    }
    public void dfs(TreeNode root){
        if(root == null) return; 
        dfs(root.left);
        dfs(root.right);
        f.put(root,root.val+g.getOrDefault(root.left, 0) + g.getOrDefault(root.right, 0));
        g.put(root, Math.max(f.getOrDefault(root.left, 0), g.getOrDefault(root.left, 0)) + Math.max(f.getOrDefault(root.right, 0), g.getOrDefault(root.right, 0)));
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        //dp[i][0] 表示当前持有股票的最大收益
        //dp[i][1] 表示没有股票处于冻结期
        //dp[i][2] 表示没有股票没有处于冷冻期
        int len = prices.length;
        int dp[][] = new int[len][3];
        dp[0][0] = -prices[0];
        for(int i = 1;i < len;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
            dp[i][1] = dp[i-1][0]+prices[i];
            dp[i][2] = Math.max(dp[i-1][1],dp[i-1][2]);
        }
        return Math.max(dp[len-1][1],dp[len-1][2]);
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        //dp[i][0] 表示这天不持有股票最大收益
        //dp[i][1] 表示这天持有股票最大收益
        int dp[][] = new int[len][2];
        dp[0][1] = -prices[0];
        for(int i = 1;i < len ;i++){
            dp[i][0] = Math.max(dp[i-1][1]+prices[i],dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][1],(i<2?0:dp[i-2][0])-prices[i]);
        }
        return dp[len-1][0];
    }
}