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
- Aggregate the points per value: taking value
vearnsv * count(v). - If you take
v, you cannot takev - 1orv + 1, so the conflict is between adjacent values on the number line. - This is exactly the House Robber recurrence over the value range
0..max(nums). - Run
dp[v] = max(dp[v - 1], dp[v - 2] + v * count(v))and returndp[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
vcontributesv * count(v), not justv. - 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.