Problem Number

740

Problem Title

Delete and Earn

LeetCode Link

https://leetcode.com/problems/delete-and-earn/

Contribution Checklist

• I have written the Approach section.
• I have written the Intuition section.
• I have included a working C++ solution.
• I will raise a PR and ensure the filename follows the convention [Number]. [Problem Title].cpp.

Approach

Build frequency array:
Count how many times each number appears in nums.
Keep track of the maximum number (maxVal) to limit DP size.

Dynamic Programming:
Let dp[i] be the maximum points we can earn considering numbers from 1 to i.
For each i ≥ 2, we have two options:
Skip i: dp[i] = dp[i-1]
Take i: dp[i] = dp[i-2] + f[i] * i (we skip i-1 because taking i deletes i-1)
Base case: dp[1] = f[1]

Return result:
dp[maxVal] is the maximum points we can earn.

Intuition

The problem is similar to the "House Robber" problem but applied to numbers: if you take a number x, you cannot take x-1 or x+1.
The key insight is to transform the input array into a frequency array f[i], where f[i] counts how many times i appears. Now, instead of worrying about positions in the array, we only care about values. The maximum points we can earn for value i is f[i] * i, and we can use dynamic programming to decide whether to "take" or "skip" each number.

Solution in C++

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int m = 10001;
        int n = nums.size();
        int maxVal = 0;
        vector<int> f(m, 0);
        vector<int> dp(m + 1, 0);

        for (int i = 0; i < n; i++) {
            f[nums[i]]++;
            maxVal = max(maxVal, nums[i]);
        }

        dp[1] = f[1];
        for (int i = 2; i <= maxVal; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + f[i] * i);
        }

        return dp[maxVal];
    }
};