Problem Overview

You are given an integer array nums.

You can perform the following operation any number of times:

• Pick a number x and earn x points.

• After that, all numbers equal to x - 1 and x + 1 are deleted from the array.

Your goal is to maximize the total points.

This problem is frequently asked by Google because it tests how well you convert a complex decision problem into dynamic programming.

Example

Input:

nums = [2,2,3,3,3,4]

Frequencies:

2 → appears twice → total value = 4
3 → appears three times → total value = 9
4 → appears once → total value = 4

Choosing 3 removes both 2 and 4, but earns the highest total.

Answer:

9

Approach 1: Probability / Try-All Choices Idea

At every step, you can choose any number and remove its neighbors.

Conceptually:

• Try choosing each possible number first.

• Continue choosing from the remaining array.

• Track the maximum result.

Disadvantage:

• The number of possibilities grows exponentially.

• Impossible to run for large inputs.

This approach is not practical.

Approach 2: Greedy Strategy

A greedy idea is:

• Always choose the number with the largest immediate value.

Why it fails:

• Choosing a number removes its neighbors.

• A locally best choice may block a better global combination.

Example:

nums = [1,1,2,2,2,3]

Choosing 2 looks best immediately, but it may block a better combination of 1 and 3.

Greedy does not guarantee the optimal answer.

Approach 3: Recursion and Backtracking

We can define a recursive function:

• At each step, choose a number or skip it.

• Recursively compute the best result.

Disadvantages:

• Many repeated states.

• Exponential time complexity.

• Causes time limit exceeded.

This solution is correct but inefficient.

Best Approach: Dynamic Programming

Key Insight

This problem is equivalent to the House Robber problem.

Why?

• Picking number i removes i - 1 and i + 1.

• This is exactly the same restriction as not picking adjacent houses.

Step 1: Group Values

Instead of working with the original array, group numbers:

sum[i] = total points gained by picking number i

Example:

nums = [2,2,3,3,3,4]

sum[2] = 4
sum[3] = 9
sum[4] = 4

Step 2: Apply Dynamic Programming

Define:

• prev1 = best result up to previous number

• prev2 = best result up to the number before that

Transition:

current = max(prev1, prev2 + sum[i])

This means:

• Either skip i

• Or take i and add its value to the best result before i - 1

Time and Space Complexity

• Time: O(n)

• Space: O(n) for grouping, O(1) for DP states

Final Code (Dynamic Programming)

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        if (nums.empty()) return 0;

        int mx = 0;
        for (int x : nums) {
            if (x > mx) mx = x;
        }

        vector<int> sum(mx + 1, 0);
        for (int x : nums) {
            sum[x] += x;
        }

        int prev2 = 0;
        int prev1 = 0;

        for (int i = 1; i <= mx; i++) {
            int curr = max(prev1, prev2 + sum[i]);
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }
};