740. Delete and Earn 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int deleteAndEarn(int[] nums) {
        int max = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
        }

        int[] counts = new int[max + 1];
        for (int num : nums) {
            counts[num]++;
        }

        int[] dp = new int[max + 1];
        dp[1] = counts[1] * 1;
        for (int i = 2; i <= max; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * counts[i]); // 不选与选当前元素
        }

        return dp[max];
    }
}

References

740. Delete and Earn