Rust Gym Leetcode 740 Delete and Earn Rust Solution

740. Delete and Earn

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

Input: nums = [3,4,2]
Output: 6
Explanation: Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points.
6 total points are earned.

Example 2:

Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.

Constraints:

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

740. Delete and Earn

struct Solution;

impl Solution {
    fn delete_and_earn(nums: Vec<i32>) -> i32 {
        let n = 10001;
        let mut sum: Vec<i32> = vec![0; n];
        let mut dp: Vec<i32> = vec![0; n];
        for x in nums {
            sum[x as usize] += x;
        }
        dp[1] = sum[1];
        for i in 2..n {
            dp[i] = i32::max(sum[i] + dp[i - 2], dp[i - 1]);
        }
        dp[n - 1]
    }
}

#[test]
fn test() {
    let nums = vec![3, 4, 2];
    let res = 6;
    assert_eq!(Solution::delete_and_earn(nums), res);
    let nums = vec![2, 2, 3, 3, 3, 4];
    let res = 9;
    assert_eq!(Solution::delete_and_earn(nums), res);
}