# Delete and Earn

## Problem#

Given an array of integer `nums`. Our task is to maximize the number of points we can get by following below operation any number of times:

• Pick any `nums[i]` and delete it to earn `nums[i]` points. Afterwards, you must delete every element equal to `nums[i] - 1` and every element equal to `nums[i] + 1`.

Return the maximum number of points we can earn by applying the above operation some number of times.

For example,

```Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = .
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.
```
```Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = .
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.
```

Constraints:

• `1 <= nums.length <= 2 * 104`
• `1 <= nums[i] <= 104`

## Solution#

In the description there is a phrase `you must delete every element equal...`. To simplify operating with every element at once, the most logical data structure is `map` that can be implemented as `Dictionary` in C# or `HashMap` in Java.

This will form our preprocessing step as illustrated in image below. With input `nums = [2, 2, 4, 3, 3, 3]`, it might be tempting to sort map by the key. However, we don’t need it since we are going to work with index ranging from `0` to the maximum number of the key which is `4` in this case.

Similar to previous House Robber problem, we could determine current state based on previous states. At any point (num) we have two choices:

• Compute total points (gain) for current number plus maximum number of points we get from previous two number, i.e., `DeleteAndEarn(maxNumber - 2)` or
• Compute maximum number of points we get from previous number, i.e., `DeleteAndEarn(maxNumber - 1)`

To summarize:

`DeleteAndEarn(maxNumber) = Math.Max(DeleteAndEarn(maxNumber - 1), DeleteAndEarn(maxNumber - 2) + gain)`

where `gain` is total points we earn from current number. If current number doesn’t exist in the map, it will return 0.

This will lead us to our first solution (Brute Force) before we perform any optimization.

### Brute Force# ``````public int DeleteAndEarn(int[] nums)
{
int maxNumber = 0;
Dictionary<int, int> points = new Dictionary<int, int>();

foreach (int num in nums)
{
points[num] = points.GetValueOrDefault(num, 0) + num;
maxNumber = Math.Max(maxNumber, num);
}

return DeleteAndEarn(maxNumber);

int DeleteAndEarn(int maxNumber)
{
if (maxNumber == 0)
return 0;

if (maxNumber == 1)
return points.GetValueOrDefault(1, 0);

int gain = points.GetValueOrDefault(maxNumber, 0);
return Math.Max(DeleteAndEarn(maxNumber - 1), DeleteAndEarn(maxNumber - 2) + gain);
}
}
``````

#### Complexity Analysis#

Suppose `N` is the maximum number in `nums`.

• Time Complexity: At each step we generate two subtree and the height of the tree is `N`. The total number of generated nodes is 2N. Since, we traverse all the nodes, then the complexity will be O(2N).
• Space Complexity: The complexity will be the same with O(recursion depth), thus it will be O(N).

### Top-down Dynamic Programming# ``````public int DeleteAndEarn(int[] nums)
{
int maxNumber = 0;
Dictionary<int, int> points = new Dictionary<int, int>();

foreach (int num in nums)
{
points[num] = points.GetValueOrDefault(num, 0) + num;
maxNumber = Math.Max(maxNumber, num);
}

int[] maxPoints = new int[maxNumber + 1];

return DeleteAndEarn(maxNumber);

int DeleteAndEarn(int maxNumber)
{
if (maxNumber == 0)
return 0;

if (maxNumber == 1)
return points.GetValueOrDefault(1, 0);

if (maxPoints[maxNumber] > 0)
return maxPoints[maxNumber];

int gain = points.GetValueOrDefault(maxNumber, 0);
maxPoints[maxNumber] = Math.Max(DeleteAndEarn(maxNumber - 1), DeleteAndEarn(maxNumber - 2) + gain);

return maxPoints[maxNumber];
}
}
``````

#### Complexity Analysis#

Suppose `N` is the maximum number in `nums`.

• Time Complexity: Since we cache each `DeleteAndEarn(i)`, then we will perform at most N recursive calls, thus the complexity is O(N).
• Space Complexity: The complexity will be the same with O(recursion depth), thus it will be O(N).

### Bottom-up Dynamic Programming#

This approach is the most efficient since we can avoid recursion stack overhead by using `for-loop` iteration linearly.

The solution is also similar to previous House Robber Bottom Up Dynamic Programming solution.

The algorithm works as follows:

1. We provide `maxPoints` array to cache the result of every state
2. Initialize `maxPoints` for `0` and `1`
3. Then linearly we will compute `maxPoints` for every number from 2 to the maximum number in `nums` based on our preprocessing step. The result will be stored in `maxPoints` cache where it can be reused to compute future state, i.e.,

`maxPoints[num] = Math.Max(maxPoints[num - 1], maxPoints[num - 2] + gain)`.

``````public int DeleteAndEarn(int[] nums)
{
int maxNumber = 0;
Dictionary<int, int> points = new Dictionary<int, int>();

foreach (int num in nums)
{
points[num] = points.GetValueOrDefault(num, 0) + num;
maxNumber = Math.Max(maxNumber, num);
}

int[] maxPoints = new int[maxNumber + 1];
maxPoints = 0;
maxPoints = points.GetValueOrDefault(1, 0);

for (int num = 2; num < maxPoints.Length; num++)
{
int gain = points.GetValueOrDefault(num, 0);
maxPoints[num] = Math.Max(maxPoints[num - 1], maxPoints[num - 2] + gain);
}

return maxPoints[maxNumber];
}
``````

#### Complexity Analysis#

Suppose `N` is the maximum number in `nums`.

• Time Complexity: Since we iterate linearly up to `N`, then the complexity is O(N).
• Space Complexity: O(N) since we allocate memory as many as `N+1` to array `maxPoints` for caching.