# 6-liner O(N*logk) time, optimized space O(k) (NOT fixed range!)

• 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;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.