Welcome to Subscribe On Youtube
740. Delete and Earn
Description
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 earnnums[i]
points. Afterwards, you must delete every element equal tonums[i]  1
and every element equal tonums[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}
Solutions
Intuition: If we take a number, we will take all of the copies of it.
First calculate the sum of each number as sums, and keep updating two dp arrays: select and nonSelect
sums[i]
represents the sum of elements whose value is i;select[i]
represents the maximum sum of processing from 0 to i if the number i is selected;nonSelect[i]
represents the maximum sum of processing from 0 to i if the number i is not selected;
Then we have the following conclusions:
 If i is selected, then i1 must not be selected;
 If you do not choose i, then i1 can choose or not, so we choose the larger one;
select[i] = nonSelect[i  1] + sums[i];
nonSelect[i] = Math.max(select[i  1], nonSelect[i  1]);

class Solution { public: int deleteAndEarn(vector<int>& nums) { vector<int> vals(10010); for (int& num : nums) { vals[num] += num; } return rob(vals); } int rob(vector<int>& nums) { int a = 0, b = nums[0]; for (int i = 1; i < nums.size(); ++i) { int c = max(nums[i] + a, b); a = b; b = c; } return b; } };

class Solution: def deleteAndEarn(self, nums: List[int]) > int: mx = inf for num in nums: mx = max(mx, num) total = [0] * (mx + 1) for num in nums: total[num] += num first = total[0] second = max(total[0], total[1]) for i in range(2, mx + 1): cur = max(first + total[i], second) first = second second = cur return second

func deleteAndEarn(nums []int) int { max := func(x, y int) int { if x > y { return x } return y } mx := math.MinInt32 for _, num := range nums { mx = max(mx, num) } total := make([]int, mx+1) for _, num := range nums { total[num] += num } first := total[0] second := max(total[0], total[1]) for i := 2; i <= mx; i++ { cur := max(first+total[i], second) first = second second = cur } return second }