Delete and Earn
Given an array of integers, you can delete any number from the array and earn the number of points equal to the number you deleted. However, if you delete a number, you cannot delete any other number that is one more or one less than the deleted number. Find the maximum number of points you can earn.
Constraints:
- 1 <= nums.length <= 20000
- 1 <= nums[i] <= 10^4
Examples:
Input: [3,4,2]
Output: 6
Explanation: You can delete 3 and 4 to earn 7 points, but you cannot delete 2 because it is one less than 3. So, the maximum points you can earn is 6 by deleting 3 and 2, or 4 and 2.
Solutions
Dynamic Programming
The solution uses dynamic programming to keep track of the maximum points that can be earned for each number up to the maximum number in the array. It iterates through the array and updates the dp array accordingly. Finally, it returns the maximum points that can be earned for the maximum number.
int deleteAndEarn(vector<int>& nums) {
int max = 0;
for (int num : nums) {
max = std::max(max, num);
}
vector<int> dp(max + 1, 0);
for (int num : nums) {
dp[num] += num;
}
for (int i = 2;
i <= max;
i++) {
dp[i] = std::max(dp[i - 1], dp[i - 2] + dp[i]);
}
return dp[max];
}Follow-up:
What if the array is very large and we need to optimize the space complexity?
