This is the 9th day of my participation in the August Wen Challenge.More challenges in August

The title

Given an array of integers, nums, you can do something with it.

In each operation, select any NUMs [I], delete it and gain nums[I] points. After that, you must remove all elements equal to nums[I] -1 and nums[I] + 1.

You start out with zero points. Returns the maximum number of points you can earn from these operations.

The sample

Input: nums = [3,4,2] Output: 6 Explanation: 4 is removed for 4 points, so 3 is also removed. After that, delete 2 for 2 points. Six points in total. Input: nums = [2,2,3,3,3,4] Output: 9 After that, deleting 3 more gets 3 points, and deleting 3 more gets 3 points. A total of 9 points were scored.Copy the code

prompt

  • 1 <= nums.length <= 2 *
    1 0 4 10^4
  • 1 <= nums[i] <=
    1 0 4 10^4

Their thinking

198. What is the meaning of this passage?

If you don’t know, you can take a look at that one. (I would never say to increase reading.)}(I would never say to increase reading.)

The difference is that the value of each house is fixed. In this problem, we need to do statistics again before derivation. We need to count all the elements with the same value and sort them so that we can skip the adjacent elements later.

Code implementation

class Solution {
    public int deleteAndEarn(int[] nums) {
        // boundary judgment
        if(nums.length == 1) {return nums[0];
        }

        // Get the value range
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for(int num : nums){
            if(max < num){
                max = num;
            }
            if(min > num){ min = num; }}// add the same elements
        int[] counts = new int[max - min + 1];
        for(int num : nums){
            counts[num - min] += num;
        }

        / / state transition: dp [I] = Max (dp] [I - 1, dp [I - 2) + counts [I])
        int front = counts[0], after = Math.max(counts[0], counts[1]);
        for(int i = 2; i <= max - min; ++i){
            int tmp = Math.max(after, front + counts[i]);
            front = after;
            after = tmp;
        }

        returnafter; }}Copy the code

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

Title source: leetcode-cn.com/problems/de…