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]);

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