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

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 i-1 must not be selected;
• If you do not choose i, then i-1 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]);

• C++
• Python
• Go

• 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
  }
  

All Problems

All Solutions