Leetcode 740) Delete and Earn

13 Sep 2021 in Algorithms

My solution

class Solution {
    public int deleteAndEarn(int[] nums) {
        //sort first
        Arrays.sort(nums);

        int globalMax =0;
        List<Integer> unique = new ArrayList<>();
        Map<Integer,Integer> m = new HashMap<>();

        for(int i =0;i<nums.length;i++){
            int cntAll =nums[i];
            unique.add(nums[i]);
            while( i+1 <nums.length && nums[i]==nums[i+1]){
                cntAll+=nums[i];
                i++;
            }

            m.put(nums[i],cntAll);            
        }

        int l=unique.size();
        int dp[] = new int[l+1];

        //using unique array
        dp[0]=0;
        dp[1]=m.get(unique.get(0));

        for(int i=2;i<l+1;i++){
            if(unique.get(i-2)+1<unique.get(i-1)){
                //number is not sequential.
                dp[i]=dp[i-1]+m.get(unique.get(i-1));
            }else{
                //number is continuous
                dp[i]= Math.max(dp[i-1],dp[i-2]+m.get(unique.get(i-1)));
            }
        }

        return dp[dp.length-1];
    }
}

Other Answer

• I was thinking about this approach either.

class Solution {
    public int deleteAndEarn(int[] nums) {
        int[] freq = new int[10001];
        for (int num : nums) {
            freq[num]++;
        }
        int avoid = 0, using = 0, prev = -1;
        for (int i=0;i<=10000;i++) {
            if (freq[i]>0) {
                int max = Math.max(avoid, using);
                if (i-1 != prev) {
                    using = i * freq[i] + max;
                    avoid = max;
                } else {
                    using = i * freq[i] + avoid;
                    avoid = max;
                }
                prev = i;
            }
        }
        return Math.max(avoid, using);
    }
}