Delete and Earn Medium 0 attempts
LeetCode ↗

Delete and Earn

Medium Dynamic ProgrammingMemoization LeetCode

You're given an integer array nums. In each move, choose some value present in the array, add that value to your score for every occurrence of it, and then remove every occurrence of that value along with any elements equal to value-1 and value+1. Keep making moves until no elements remain, and return the maximum total score achievable.

Input Format
Implement deleteAndEarn(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
nums = [3,4,2]
Output
6

Example 2

Input
nums = [2,2,3,3,3,4]
Output
9
Constraints
  • 1 <= nums.length <= 2 * 10^4
  • 1 <= nums[i] <= 10^4
Test Cases (2)
Case 1
Args: [[3,4,2]] Expected: 6
Case 2
Args: [[2,2,3,3,3,4]] Expected: 9
Topics
Dynamic ProgrammingMemoization

House Robber on Frequency Array

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

javascript
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.

JavaScript