740 Delete and Earn
You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:
Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1. Return the maximum number of points you can earn by applying the above operation some number of times.
Example 1:
Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.
Example 2:
Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.
动态规划。现排序，然后统计每个点和个数。先求出前 2 个点的最优解，然后从第 3 个点开始从左到右遍历，如果当前的点左边没有相邻的点，则到当前点的最优解为删除当前的点加上到达上一个点的最优解，否则为到达上上个点的最优解加上删除当前点和到达上一个点的最优解的最大者。
class Solution {
public int deleteAndEarn(int[] nums) {
Arrays.sort(nums);
ArrayList<int[]> list = count(nums);
int[] dp=new int[list.size()];
dp[0]=list.get(0)[0]*list.get(0)[1];
if(list.size()==1) return dp[0];
dp[1]=list.get(1)[0]*list.get(1)[1];
if(list.get(1)[0]-list.get(0)[0]==1){
dp[1]=dp[1]>dp[0]?dp[1]:dp[0];
}else{
dp[1]=dp[0]+dp[1];
}
for(int i=2;i<list.size();++i){
int[] arr=list.get(i);
int cur=arr[0]*arr[1];
if(arr[0]-list.get(i-1)[0]==1){
dp[i]=Math.max(cur+dp[i-2],dp[i-1]);
} else {
dp[i]=cur+dp[i-1];
}
}
return dp[list.size()-1];
}
private ArrayList<int[]> count(int[] nums){
ArrayList<int[]> list=new ArrayList<>();
int index=0;
int cur=nums[index];
int count=0;
while(index<nums.length){
if(nums[index]==cur){
count++;
index++;
} else {
list.add(new int[]{cur,count});
cur=nums[index];
index++;
count = 1;
}
}
list.add(new int[]{cur,count});
return list;
}
}