740. Delete and Earn

https://leetcode.com/problems/delete-and-earn/

其实这是house robber的拓展题，如果你take了一个它的邻居就不能take了，就这么简单

重复的元素其实可以一次性拿走

class Solution {
    public int deleteAndEarn(int[] nums) {
        Arrays.sort(nums);
        Map<Integer, Integer> freqs = new HashMap<>();
        int len = 0;
        freqs.put(nums[len], freqs.getOrDefault(nums[len], 0)+1);
        for (int j = 1; j < nums.length; j++) {
            freqs.put(nums[j], freqs.getOrDefault(nums[j], 0)+1);
            if (nums[len] != nums[j]) {
                nums[++len] = nums[j];
            }
        }
        len++;
        int[] dp = new int[len+1]; //dp[i]是前i个最大值，不管拿不拿i
        dp[1] = nums[0]*freqs.get(nums[0]);
        for (int i = 1; i < len; i++) {
            int max = dp[i];
            int maxprev = 0;
            //这里得往回找到第一个不相等的数，
            // 如果不想这么麻烦也可以直接把不存在的neighbor也加进来，
            // 也就是用nums*freqs填满整个[0,max(nums)]空间，不存在的数freqs是0就好了
            // 这样问题就完全化为了house robber，只不过会很费空间就是了，
            // 但是好处是不用sort了，毕竟nums可以直接放到对应的位置
            for (int j = i-1; j >= 0; j--) {
                if (nums[j] != nums[i]-1) {
                    maxprev = dp[j+1];
                    break;
                }
            }
            dp[i+1] = Math.max(max, maxprev+nums[i]*freqs.get(nums[i]));
        }
        return dp[len];
    }
}