Delete and earn

Array Hash Table Dynamic Programming

57.1% acceptance

Feb 21, 2026

7937

404

You are given an integer array nums. You want to maximize the number of points you get 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 by applying the above operation some number of times.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

/*
 * You are given an integer array nums. You want to maximize the number of points you get 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 by applying the above operation some number of times.
 * Example 1:
 * Input: nums = [3,4,2]
 * Output: 6
 * Explanation: You can perform the following operations:
 * - Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
 * - Delete 2 to earn 2 points. nums = [].
 * You earn a total of 6 points.
 * Example 2:
 * Input: nums = [2,2,3,3,3,4]
 * Output: 9
 * Explanation: You can perform the following operations:
 * - Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
 * - Delete a 3 again to earn 3 points. nums = [3].
 * - Delete a 3 once more to earn 3 points. nums = [].
 * You earn a total of 9 points.
 * Constraints:
 * 1 <= nums.length <= 2 * 104
 * 1 <= nums[i] <= 104
 */
impl Solution {
  pub fn delete_and_earn(nums: Vec<i32>) -> i32 {
    let max_val = *nums.iter().max().unwrap() as usize;
    let mut sum = vec![0i64; max_val + 1];
    for &n in &nums {
      sum[n as usize] += n as i64;
    }
    if max_val == 0 { return 0; }
    if max_val == 1 { return sum[1] as i32; }
    let mut prev2 = sum[0];
    let mut prev1 = sum[0].max(sum[1]);
    for i in 2..=max_val {
      let cur = prev1.max(prev2 + sum[i]);
      prev2 = prev1;
      prev1 = cur;
    }
    prev1 as i32
  }
}