Delete and Earn | Problems

Given an array of integers, you can pick any element to earn its value, but you must also delete all elements equal to value-1 and value+1. Return the maximum points.

Example: nums = [3,4,2] → Output: 6 (delete 4, earn 3+3=6... wait, pick 2 and 3)

Sample Input

—

Sample Output

—

Constraints

1 <= nums.length <= 2 * 10^4
1 <= nums[i] <= 10^4

Test Cases

Case 1

Args: [[3,4,2]] Expected: 6

Case 2

Args: [[2,2,3,3,3,4]] Expected: 9

Topics

Dynamic Programming Memoization

House Robber on Frequency Array

Transform to a frequency-weighted array and solve like House Robber.

function deleteAndEarn(nums) {
  const max = Math.max(...nums);
  const sums = Array(max + 1).fill(0);
  for (const n of nums) sums[n] += n;
  let prev = 0, curr = 0;
  for (let i = 0; i <= max; i++) [prev, curr] = [curr, Math.max(curr, prev + sums[i])];
  return curr;
}

Time: O(n + max) | Space: O(max)

Saved in this browser only. Private to you.