Given an array nums of integers, you can perform operations on the array.
In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.
You start with 0 points. Return the maximum number of points you can earn by applying such operations.
Example 1:
Input: nums = [3, 4, 2]
Output: 6
Explanation:
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.
Example 2:
Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation:
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.
Note:
- The length of
numsis at most20000. - Each element
nums[i]is an integer in the range[1, 10000].
Runtime: 4852 ms, faster than 0.72% of C++ online submissions for Delete and Earn.
自以为做了一个区间DP，结果并不是这样做。
//
// Created by yuxi on 2019/1/22.
// #include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std; class Solution {
public:
unordered_map<int,int> mp;
unordered_map<int,int> memo;
int deleteAndEarn(vector<int>& nums) {
if(nums.empty()) return ;
for(int x : nums) mp[x]++;
vector<int> keys;
for(auto it = mp.begin(); it != mp.end(); it++) keys.push_back(it->first);
sort(keys.begin(),keys.end());
vector<vector<int>> dp(keys.size(), vector<int>(keys.size(),));
for(int k=; k<keys.size(); k++) {
for(int i=; i<keys.size(); i++) {
int j = i - k;
if(j < ) continue;
if(i == j) {
dp[j][i] = keys[i] * mp[keys[i]];
continue;
}
for(int l = j; l < i; l++) {
if(keys[l] == keys[l+]-) {
if(l+ == i) dp[j][i] = max(dp[j][i], max(dp[j][l],dp[i][i]));
else dp[j][i] = max(dp[j][i], dp[j][l]+dp[l+][i]);
}else {
dp[j][i] = max(dp[j][i], dp[j][l]+dp[l+][i]);
}
}
}
}
return dp[][keys.size()-];
}
};
Runtime: 8 ms, faster than 87.68% of C++ online submissions for Delete and Earn.
//
// Created by yuxi on 2019/1/22.
// #include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std; class Solution {
public:
unordered_map<int,int> mp;
unordered_map<int,int> memo;
int deleteAndEarn(vector<int>& nums) {
if(nums.empty()) return ;
int maxval = ;
for(int x : nums) {
maxval = max(maxval,x);
mp[x]++;
}
vector<int> a(maxval+, );
for(auto it=mp.begin(); it != mp.end(); it++) {
a[it->first] = it->second;
}
int prev = , cur = ;
for(int i=; i<a.size(); i++) {
cur = max(cur, i > ? a[i] * i + a[i-] : a[i] * i);
a[i] = cur;
}
return cur;
}
};