# LeetCode 740: Delete and Earn

## Problem Restatement

We are given an integer array `nums`.

We may repeatedly choose a number `x`.

When we choose `x`:

1. We earn `x` points.
2. Every occurrence of `x - 1` is deleted.
3. Every occurrence of `x + 1` is deleted.

We can continue until no numbers remain.

We need to return the maximum total points we can earn.

The official problem states that after taking a value `x`, every occurrence of `x - 1` and `x + 1` becomes unavailable. ([leetcode.com](https://leetcode.com/problems/delete-and-earn/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of integers `nums` |
| Output | Maximum obtainable points |
| Choosing `x` | Earns `x` points per occurrence chosen |
| Side effect | Deletes all `x - 1` and `x + 1` values |

Example function shape:

```python
def deleteAndEarn(nums: list[int]) -> int:
    ...
```

## Examples

### Example 1

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

If we choose `4`, then `3` is deleted.

That gives:

```python
4 points
```

If we choose `2`, nothing conflicts with it afterward.

Total:

```python
4 + 2 = 6
```

The answer is:

```python
6
```

### Example 2

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

The total value for each number is:

| Number | Total Points |
|---|---:|
| 2 | 4 |
| 3 | 9 |
| 4 | 4 |

If we take `3`, then `2` and `4` are removed.

That gives:

```python
9
```

If we instead take `2` and `4`, we get:

```python
4 + 4 = 8
```

So the best answer is:

```python
9
```

## First Thought: Recursive Choices

At each step, we can choose some value `x`.

Then values `x - 1` and `x + 1` become forbidden.

This looks like a recursive decision problem.

But directly simulating deletions is complicated and inefficient.

The important observation is that only the numeric values matter, not their positions in the array.

## Key Insight

Group equal numbers together.

Suppose:

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

Instead of thinking about individual elements, think about total gain per value:

```python
2 -> 4
3 -> 9
4 -> 4
```

Now the problem becomes:

```text
choose values without taking adjacent numbers
```

This is exactly the same structure as House Robber.

In House Robber:

- Robbing house `i` forbids house `i - 1` and `i + 1`.

Here:

- Taking value `x` forbids `x - 1` and `x + 1`.

So we convert the problem into a linear DP over values.

## Algorithm

1. Count the total points contributed by each value.
2. Let:

```python
points[x]
```

store the total score from value `x`.

3. Process values from `0` to `max(nums)`.

For each value `x`:

- Either skip it.
- Or take it and add `points[x]` to the best answer up to `x - 2`.

Use House Robber DP:

```python
dp[x] = max(
    dp[x - 1],
    dp[x - 2] + points[x]
)
```

Return the final DP value.

## Correctness

For every value `x`, all occurrences of `x` should either be taken together or skipped together.

If we take one occurrence of `x`, then all occurrences of `x - 1` and `x + 1` become unusable. Taking additional copies of `x` has no additional restriction, so taking all copies of `x` is always optimal once we decide to take value `x`.

Therefore the problem reduces to choosing values on the number line.

For each value `x`, there are exactly two possibilities:

1. Skip `x`.
   - Then the best total remains `dp[x - 1]`.

2. Take `x`.
   - Then `x - 1` cannot be taken.
   - The best compatible earlier result is `dp[x - 2]`.
   - The total becomes `dp[x - 2] + points[x]`.

The recurrence:

```python
dp[x] = max(
    dp[x - 1],
    dp[x - 2] + points[x]
)
```

therefore considers all optimal possibilities.

The DP processes values in increasing order, so all required earlier states are already known.

Thus the final DP value equals the maximum obtainable score.

## Complexity

Let:

```python
m = max(nums)
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + m)` | Build totals once, then scan all values |
| Space | `O(m)` | Store totals and DP states |

Here `n` is the length of `nums`.

## Implementation

```python
class Solution:
    def deleteAndEarn(self, nums: list[int]) -> int:
        if not nums:
            return 0

        max_num = max(nums)

        points = [0] * (max_num + 1)

        for num in nums:
            points[num] += num

        dp = [0] * (max_num + 1)

        dp[0] = points[0]

        if max_num >= 1:
            dp[1] = max(points[0], points[1])

        for x in range(2, max_num + 1):
            dp[x] = max(
                dp[x - 1],
                dp[x - 2] + points[x]
            )

        return dp[max_num]
```

## Code Explanation

We first handle the empty case:

```python
if not nums:
    return 0
```

Then we compute the largest value:

```python
max_num = max(nums)
```

The `points` array stores the total gain for each number:

```python
points[num] += num
```

For example:

```python
nums = [2, 2, 3]
```

produces:

```python
points[2] = 4
points[3] = 3
```

The DP array stores the best answer up to each value:

```python
dp = [0] * (max_num + 1)
```

The recurrence is:

```python
dp[x] = max(
    dp[x - 1],
    dp[x - 2] + points[x]
)
```

This means:

- Skip value `x`.
- Or take value `x` and combine it with the best non-adjacent result.

Finally:

```python
return dp[max_num]
```

returns the optimal answer over all values.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.deleteAndEarn([3, 4, 2]) == 6
    assert s.deleteAndEarn([2, 2, 3, 3, 3, 4]) == 9
    assert s.deleteAndEarn([1]) == 1
    assert s.deleteAndEarn([1, 1, 1, 2, 4, 5, 5, 5, 6]) == 18
    assert s.deleteAndEarn([8, 10, 4, 9, 1, 3, 5, 9, 4, 10]) == 37
    assert s.deleteAndEarn([]) == 0

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[3, 4, 2]` | Basic example |
| `[2, 2, 3, 3, 3, 4]` | Taking middle value beats outer values |
| `[1]` | Minimum non-empty input |
| Mixed repeated values | Checks grouped scoring |
| Larger mixed case | More complex DP transitions |
| Empty array | Edge case handling |