740. Delete and get points

Address ：

Power button https://leetcode-cn.com/problems/delete-and-earn/

subject ：

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

In every operation , Choose any one  nums[i] , Delete it and get  nums[i]  Number of points . after , You have to delete it all be equal to  nums[i] - 1 and nums[i] + 1  The elements of .

At first you have 0 Points . Return the maximum number of points you can get through these operations .

Example 1：

Input ：nums = [3,4,2] Output ：6 explain ： Delete 4 get 4 Points , therefore 3 Also deleted . after , Delete 2 get 2 Points . All in all 6 Points .

Example  2：

Input ：nums = [2,2,3,3,3,4] Output ：9 explain ： Delete 3 get 3 Points , And then we're going to delete two 2 and 4 . after , Delete again 3 get 3 Points , Delete again 3 get 3 Points . All in all 9 Points .

Tips ：

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

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/delete-and-earn
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

Select one i, Delete i-1 and i -2 , Just choose one , The next two cannot be selected , Typical  198. raid homes and plunder houses

But there are still some small details to deal with , That is, there are duplicate elements in the array , Therefore, it cannot be applied directly

So if we count the number of elements , And put the sum value in the new array

This new array can be applied

This part of the work is entrusted to   Counting sorting of sorting algorithm complete

Method 1 、 Count array + raid homes and plunder houses

#define max(a,b) ( (a) > (b) ? (a) : (b) )

int rob(int* nums, int numsSize){
	int i;
	int dp[10001]={0};
	dp[0] = nums[0];

	for(i=1; i<numsSize; i++)
	{
		if(i == 1)
			dp[i] = max(nums[0], nums[1]);
		else
			dp[i]= max(dp[i-1], dp[i-2]+nums[i]);
	}
	
	return dp[numsSize - 1];
}

int deleteAndEarn(int* nums, int numsSize){
	int i;
	int count[10001] = {0};
	int val[10001] = {0};
	
	for(i=0; i<numsSize; i++)
	{
		int idx = nums[i];
		count[idx]++;
	}
	
	for(i=0; i<10001; i++)
	{
		val[i] = i * count[i];
	}
	
	return rob(val, 10001);
}

See more brush notes