题解 | #删除相邻数字的最大分数#

import java.util.*;

/**
 * NC300 删除相邻数字的最大分数
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 相似 => NC176 打家劫舍(一)
     * @param a int整型ArrayList
     * @return int整型
     */
    public int boredom (ArrayList<Integer> a) {
        // return solution1(a);
        return solution2(a);
        // return solution3(a);
    }

    /**
     * 动态规划
     *
     * dp[i][0]表示第i种数字不选择时能得到的最多分数
     * dp[i][1]表示第i种数字要选择时能得到的最多分数
     *
     * dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1])
     *            { dp[i-1][0] + map.get(curr)                        , pre+1 == curr
     * dp[i][1] = {
     *            { Math.max(dp[i-1][0], dp[i-1][1]) + map.get(curr)  , pre+1 != curr
     *
     * @param a
     * @return
     */
    private int solution1(ArrayList<Integer> a){
        // 保证有序
        TreeSet<Integer> set = new TreeSet<Integer>();
        // 存储分数
        HashMap<Integer, Integer> map = new HashMap<>();

        for(int num: a){
            set.add(num);
            map.put(num, map.getOrDefault(num,0)+num);
        }

        int len = set.size();
        int[][] dp = new int[len+1][2];

        // 前面数字
        int pre=-1;
        // 当前数字
        int curr;
        for(int i=1; i<=len; i++){
            curr = set.pollFirst();
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
            if(pre+1 == curr){
                dp[i][1] = dp[i-1][0] + map.get(curr);
            }else{
                dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]) + map.get(curr);
            }
            pre = curr;
        }

        return Math.max(dp[len][0], dp[len][1]);
    }

    /**
     * 动态规划
     *
     * dp[i]表示到达数字i时能得到的最多分数
     *
     * dp[i] = Math.max(dp[i-1], dp[i]+dp[i-2])
     *
     * @param a
     * @return
     */
    private int solution2(ArrayList<Integer> a){
        int max = 0;
        for(int num: a){
            max = Math.max(max, num);
        }

        // init
        int[] dp = new int[max+1];
        for(int num: a){
            dp[num] += num;
        }

        for(int i=2; i<=max; i++){
            dp[i] = Math.max(dp[i-1], dp[i]+dp[i-2]);
        }

        return dp[max];
    }

    /**
     * 动态规划
     *
     * dp[i]表示到达数字i时能得到的最多分数
     *
     * dp[i] = Math.max(dp[i-1], dp[i]+dp[i-2])
     *
     * @param a
     * @return
     */
    private int solution3(ArrayList<Integer> a){
        int max = 10000;

        // init
        int[] dp = new int[max+1];
        for(int num: a){
            dp[num] += num;
        }

        for(int i=2; i<=max; i++){
            dp[i] = Math.max(dp[i-1], dp[i]+dp[i-2]);
        }

        return dp[max];
    }
}