⚡Flashcard Drill➔
NeetCode #675LC-740Medium1-D Dynamic Programming
← Back to All Problems

#675 · #740 · Delete and Earn(删除并获得点数)

📌 Problem Statement & Constraints

You are given an integer array nums. You may delete elements, earning points equal to the value deleted, but deleting a value x also removes every element equal to x - 1 or x + 1 without earning. Return the maximum points you can earn. Constraints: 1 <= nums.length <= 2 * 10^4, 1 <= nums[i] <= 10^4.

💡 Core Algorithmic Approaches

  1. Aggregate the points per value: taking value v earns v * count(v).
  2. If you take v, you cannot take v - 1 or v + 1, so the conflict is between adjacent values on the number line.
  3. This is exactly the House Robber recurrence over the value range 0..max(nums).
  4. Run dp[v] = max(dp[v - 1], dp[v - 2] + v * count(v)) and return dp[max].

💻 Benchmark Python3 Implementation

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        from collections import Counter
        cnt = Counter(nums)
        hi = max(nums)
        prev2, prev1 = 0, 0            # dp[v-2], dp[v-1] over values
        for v in range(hi + 1):
            gain = v * cnt.get(v, 0)
            prev2, prev1 = prev1, max(prev1, prev2 + gain)
        return prev1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + max(nums)): counting plus a pass over the value range.
💾 Space Complexity
O(n) for the counter, or O(max value) with a direct array.

⚠️ Interview Pitfalls & Follow-ups

  • Sorting and greedily taking the largest values: the conflict is by value, not position; [2, 3, 4] gives 6 by taking 2 and 4.
  • Forgetting to multiply by the count: value v contributes v * count(v), not just v.
  • Handling gaps incorrectly: values with zero count contribute 0 and naturally break the chain, so no special case is needed.
  • Assuming nums[i] can be 0: the constraint says >= 1, so starting the loop at 0 is safe.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems