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
nums
is at most20000
. - Each element
nums[i]
is an integer in the range[1, 10000]
.
Related Topics:
Dynamic Programming
Similar Questions:
Firstly, to avoid duplicate, store the data in a map from the number to its count.
Let dp[i]
be the max point you can get at point i
.
If num != prevNum + 1
, we can freely pick num
, then dp[i] = dp[i-1] + num * count
.
Otherwise, if we don't pick num
, dp[i] = dp[i-1]
.
Otherwise, we pick num
, dp[i] = dp[i-2] + num * count
.
So in sum:
dp[i] = num == prevNum ? max(dp[i-1], dp[i-2] + num * count) : (dp[i-1] + num * count)
// OJ: https://leetcode.com/problems/delete-and-earn/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
map<int, int> m;
for (int n : nums) m[n]++;
int prev = 0, prev2 = 0, num = INT_MIN;
for (auto &p : m) {
int cur = p.first == num + 1 ? max(prev, prev2 + p.first * p.second) : (prev + p.first * p.second);
prev2 = prev;
prev = cur;
num = p.first;
}
return prev;
}
};