A more structured brute force would look like this:

text
Function MaxPoints(available_numbers):
    If available_numbers is empty: return 0
    
    max_score = 0
    For each unique number x in available_numbers:
        current_gain = x * count(x)
        remaining = available_numbers without x, x-1, x+1
        max_score = max(max_score, current_gain + MaxPoints(remaining))
    
    Return max_score

Complexity Analysis

The time complexity is roughly O(2^N) or worse, depending on the implementation. The branching factor is high because we can potentially start with any unique number.

• Why it fails: The constraints state nums.length up to $2 \times 10^4$. An exponential solution will immediately hit a Time Limit Exceeded (TLE) error. Furthermore, this approach repeatedly solves the same subproblems (e.g., the optimal way to clear a subset of numbers is calculated multiple times).

Core Insight for Delete and Earn

The critical realization required to solve LeetCode 740 is that the order of elements in nums does not matter; only their values and frequencies matter.

1. Aggregation: If we decide to take a number x, we should take all instances of x. Taking one instance deletes x-1 and x+1 anyway, so there is no penalty for taking the remaining x's. We can pre-calculate the total value provided by each number: gain[x] = x * count(x).
2. Linearization: Once we map the input to a value-based array (where index i holds the total points for number i), the "neighbors" x-1 and x+1 become adjacent indices in this new array.
3. The Constraint: The rule "delete x-1 and x+1" translates to: You cannot pick two adjacent elements in the value-based array.

This transformation reduces the problem exactly to the House Robber problem. We iterate through numbers from $0$ to $max(nums)$. At each number i, we have two choices:

1. Take i: We gain points[i]. We cannot have taken i-1, so we add this to the max points found up to i-2.
2. Skip i: We gain nothing from i. The max points is simply whatever we achieved up to i-1.

Visual Description: Imagine the numbers are houses on a street, ordered by value ($1, 2, 3, \dots$). The amount of cash in house $i$ is the sum of all $i$'s in the original array. The police are alerted if you rob two adjacent houses ($i$ and $i-1$). The recurrence tree visualizes a decision at node $i$ branching to node $i-1$ (skip) and node $i-2$ (take).

Algorithm Strategy: DP - 1D Array (Fibonacci Style)

1. Data Preparation:

   • Find the maximum value inside nums to determine the range of our DP array (let's call this maxVal).
   • Create an array sums of size maxVal + 1.
   • Iterate through nums and populate sums. For every num in nums, add num to sums[num]. Now, sums[i] represents the total points earned if we choose to delete the number i.

2. State Definition:

   • Let dp[i] represent the maximum points achievable considering only numbers from $0$ to $i$.

3. Recurrence Relation:

   • To calculate dp[i], we compare:
     • Skip i: Value is dp[i-1].
     • Take i: Value is sums[i] + dp[i-2].
   • Formula: dp[i] = max(dp[i-1], dp[i-2] + sums[i]).

4. Base Cases:

   • dp[0] = sums[0] (Usually 0, as input constraints say nums[i] >= 1).
   • dp[1] = max(sums[0], sums[1]) (or just sums[1] if 0 is excluded).

5. Space Optimization:

   • Notice that to calculate the current state, we only need the previous two states. We don't need the full dp array. We can maintain two variables, twoBack (representing dp[i-2]) and oneBack (representing dp[i-1]), updating them as we iterate.

Execution Flow

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

1. Preprocessing:

   • Max value is 4.
   • sums array (indices 0 to 4): [0, 0, 4, 9, 4].
     • sums[2] = 2 + 2 = 4
     • sums[3] = 3 + 3 + 3 = 9
     • sums[4] = 4

2. Initialization:

   • twoBack (dp[0]) = 0
   • oneBack (dp[1]) = 0

3. Iteration:

   • i = 2:
     • Option A (Skip 2): oneBack = 0.
     • Option B (Take 2): sums[2] + twoBack = 4 + 0 = 4.
     • Max is 4.
     • Update: twoBack = 0, oneBack = 4.
   • i = 3:
     • Option A (Skip 3): oneBack = 4.
     • Option B (Take 3): sums[3] + twoBack = 9 + 0 = 9.
     • Max is 9.
     • Update: twoBack = 4, oneBack = 9.
   • i = 4:
     • Option A (Skip 4): oneBack = 9.
     • Option B (Take 4): sums[4] + twoBack = 4 + 4 = 8.
     • Max is 9.
     • Update: twoBack = 9, oneBack = 9.

4. Result: Return oneBack, which is 9.

Proof of Correctness

The correctness relies on the Optimal Substructure property. For any number i, the optimal solution for the range [0...i] must be derived from the optimal solutions of its sub-problems ([0...i-1] and [0...i-2]).

Since taking number i strictly invalidates i-1 but has no effect on i-2, these two choices (take i or skip i) cover the entire solution space for the added element. By induction, if the base cases are correct (which they are trivially), and the transition logic covers all valid moves while maximizing the local decision, the final result at dp[maxVal] will be the global maximum.

Reference Implementation

C++ Solution for LeetCode 740

cpp
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int maxVal = 0;
        for (int num : nums) {
            maxVal = max(maxVal, num);
        }

        // sums[i] stores the total points gained by taking all instances of number i
        vector<int> sums(maxVal + 1, 0);
        for (int num : nums) {
            sums[num] += num;
        }

        // Standard Fibonacci-style DP variables
        int twoBack = 0; // Represents dp[i-2]
        int oneBack = sums[0]; // Represents dp[i-1] (conceptually dp[0])

        // Iterate from 1 to maxVal
        // Note: For i=1, the logic is max(sums[1] + twoBack, oneBack)
        // If we treat sums[0] as index 0, loop starts at 1
        for (int i = 1; i <= maxVal; ++i) {
            int current = max(oneBack, twoBack + sums[i]);
            twoBack = oneBack;
            oneBack = current;
        }

        return oneBack;
    }
};

Java Solution for LeetCode 740

java
class Solution {
    public int deleteAndEarn(int[] nums) {
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        // sums[i] will store i * count(i)
        int[] sums = new int[maxVal + 1];
        for (int num : nums) {
            sums[num] += num;
        }

        // DP Initialization
        // twoBack represents the max points ending at i-2
        // oneBack represents the max points ending at i-1
        int twoBack = 0;
        int oneBack = sums[0];

        for (int i = 1; i <= maxVal; i++) {
            int take = sums[i] + twoBack;
            int skip = oneBack;
            
            int current = Math.max(take, skip);
            
            twoBack = oneBack;
            oneBack = current;
        }

        return oneBack;
    }
}

Python Solution for LeetCode 740

python
class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        if not nums:
            return 0
            
        max_val = max(nums)
        sums = [0] * (max_val + 1)
        
        # Precompute total points for each number
        for num in nums:
            sums[num] += num
            
        two_back = 0
        one_back = sums[0]
        
        for i in range(1, max_val + 1):
            # Recurrence: max(skip current, take current + value from i-2)
            current = max(one_back, two_back + sums[i])
            two_back = one_back
            one_back = current
            
        return one_back