Delete and Earn

Maximize points by deleting numbers and their neighbors with a classic DP strategy.

dynamic-programming array hash-map optimization

You are given an integer list `nums`. You want to maximize the number of points you earn by performing the following operation any number of times:
- Pick any element `x` in the current list and delete it to earn `x` points.
- After picking `x`, you must delete **all** elements equal to `x - 1` and `x + 1` (if they exist) from the list. Those deleted neighbors earn you no points.

You start with 0 points. Return the maximum number of points you can earn.

Implement the function `def delete_and_earn(nums: list[int]) -> int:`. The function should return an integer representing the maximum points.

**Note:** Deleting a number earns points for each occurrence of that number you pick. For example, if `nums = [3, 4, 2]`, picking `3` earns 3 points and deletes all `2`s and `4`s, leaving `[3]`. You can then pick the remaining `3` to earn another 3 points, for a total of 6.

You may assume the array is non-empty.

Constraints

- `1 <= len(nums) <= 10^5`
- `0 <= nums[i] <= 10^4`
- The function should run in O(M + N) time where M is the maximum value in `nums` and N is the length of `nums`, and use O(M) extra space (or O(U) where U is the number of unique values).

Example

```python
>>> delete_and_earn([3, 4, 2])
6
>>> delete_and_earn([2, 2, 3, 3, 3, 4])
9
>>> delete_and_earn([5])
5
>>> delete_and_earn([0, 0])
0
```

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of each number as having a total value equal to its value times its frequency.

If you choose a number, you cannot choose its immediate neighbors. This is similar to the House Robber problem.

Build an array where index i stores the total points available from value i, then apply a classic DP with two variables.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.