This question can be reduced to LC 198. House Robber. Try solving it before proceeding if you haven’t.
Key observations:
- The order of
numsdoes not matter - If we decide to pick
nums[i]then we can pick all occurrences ofnums[i]without any more harm nums[i]is in the range [1, 10000]
Since the order of nums does not matter and if we decide to pick nums[i], we can pick all its occurrences, let us store the frequency of each number in nums. We can either use a map (hash table) to store them of simply an array of length 100001 as nums[i] is in the range 1 to 10000. Let’s store them in an array as we would need to iterate through the numbers in ascending order as you’ll see below.
Define dp[i] as maximum points achieved by considering numbers from 1..i. For a number i, we have two choices:
- Pick that number: we cannot pick the number i-1 now but we get points equal to
i*freq[i]. So total points:dp[i-2] + i*freq[i] - Do not pick that number: total points in this case remain same as
dp[i-1]
int deleteAndEarn(vector<int>& nums) {
vector<int> freq(100001, 0);
vector<int> dp(100001, 0);
for (auto i : nums) freq[i]++;
dp[1] = freq[1];
for (int i=2; i<100001; i++)
dp[i] = max(dp[i-2]+i*freq[i], dp[i-1]);
return dp[100000];
}
Time complexity: O(1)
Space complexity: O(1)