Description (leetcode)

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 * 10^4
  • 1 <= nums[i] <= 10^4

submission

// we solve this by state machine thinking
// first we collect numbers by their value
// then we iterate through each of them
// in each step, we have several state and corresponding
// options
// take: we have taken the previous number, we can only skip
// the current one, after the current one, we transition to
// skip state.
// skip: we have not taken the previous number, in turn we can
// take the current number, and we must choose take the current
// number or not, so we compare take & (skip + current), and
// choose the maxmium
impl Solution {
    pub fn delete_and_earn(nums: Vec<i32>) -> i32 {
        // by question constraints, we have 10000
        let mut cnt = vec![0; 10001];
        for n in nums {
            cnt[n as usize] += n;
        }
        cnt.into_iter()
            .fold((0, 0), |(skip, take), val| {
                // take -> skip
                // max(take, skip + val) -> take
                (take, take.max(skip + val))
            })
            .1
            // from our transition we can see take is always
            // bigger than skip
    }
}