Even though the integer `nums[i]`

has range `[1, 10000]`

, the following code deals without range restriction.

The key is to use a `std::map`

to store sums of only distinct values (instead of array allocation of max range `10000`

regardless whether a value shows up in the range).

The DP process is similar to House Robber, but we need to check whether two keys in map `sum`

are adjacent, i.e., `i->first == prev(i)->first+1`

for each iterator `i`

.

**NOTE:**

- The DP equation is same as House Robber only for adjacent keys.
- Only need
`O(k)`

space (`k =`

number of distinct values in`nums`

) - No need to keep all DP results since the recursion order is just
`2`

.

```
int deleteAndEarn(vector<int>& nums)
{
// get sum for each distinct non-zero value
map<int, int> sum;
for (int num : nums) if (num) sum[num] += num;
// initial values for DP
int res0 = 0, res1 = 0, res = sum.begin()->second;
for (auto i = sum.begin()++; i != sum.end(); i++, res0 = res1, res1 = res)
res = (i->first == prev(i)->first+1)? max(res1, res0 + i->second) : res1 + i->second;
return res;
}
```