Delete and Earn

Share

Given an integer array nums, take any nums[i] to earn nums[i] points, but delete every element equal to nums[i]-1 and nums[i]+1. Find maximum points you can earn.

Example 1
Input: [3,4,2] → Output: 6 (take 4, delete 3 and 5, take 2)
Example 2
Input: [2,2,3,3,3,4] → Output: 9

Solution Approach

Convert to "house robber" problem. Sum all values of each number into points[]. Then find max points from this 1D array (cannot take adjacent values).

  • Build points[] where points[i] = i * count(i in nums).
  • Find max(points[i-1], points[i-2] + points[i]) from index 2 onward.
  • This is identical to the House Robber problem.
Java
class Solution {
    public int deleteAndEarn(int[] nums) {
        int max = 0;
        for (int n : nums) max = Math.max(max, n);
        int[] points = new int[max + 1];
        for (int n : nums) points[n] += n;
        int prev2 = 0, prev1 = 0;
        for (int p : points) {
            int curr = Math.max(prev1, prev2 + p);
            prev2 = prev1; prev1 = curr;
        }
        return prev1;
    }
}
  • Time Complexity: O(N + max(nums))
  • Space Complexity: O(max(nums))