Dynamic Programming - Delete and Earn

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.

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

Input: [2,2,3,3,3,4] → Output: 9

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.

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))