DSA problem
Delete and Earn
You are given an integer array nums. You want to maximize the number of points you can earn by performing the following 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 you can earn.
The trick is to notice that picking any one occurrence of value v immediately forbids all of v - 1 and v + 1, but it does NOT forbid taking the other occurrences of v itself. So once you decide to "take" value v at all, the rational move is to take every single copy of v in one shot.
This observation reduces the problem to deciding, for each distinct value v in the array, whether to take v (gaining v * count[v] points) or skip it. Adjacent values v - 1 and v + 1 are mutually exclusive with v. That is precisely the House Robber recurrence on a value-indexed bucket array!
Step 1: bucket-sum the input — bucket[v] is the total points earnable by taking value v (v multiplied by its frequency). Step 2: run the standard House Robber DP across bucket[0 .. maxVal], using two rolling variables: dp[v] = max(dp[v - 1], dp[v - 2] + bucket[v]). The answer is the final value of dp. This runs in O(n + M) time and O(M) space where M = max(nums).
Examples
nums = [3,4,2]6nums = [2,2,3,3,3,4]9nums = [1,1,1,2,4,5,5,5,6]18Constraints
- 1 <= nums.length <= 2 * 10^4
- 1 <= nums[i] <= 10^4
- Each element in nums is a positive integer.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.