LeetCode 0740. Delete and Earn Solution in Java, C++, Python & Go | Explanation + Code

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

Solution 1

PythonJavaC++Go

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(code-box)

class Solution { public int deleteAndEarn(int[] nums) { if (nums.length == 0) { return 0; } int[] sums = new int[10010]; int[] select = new int[10010]; int[] nonSelect = new int[10010]; int maxV = 0; for (int x : nums) { sums[x] += x; maxV = Math.max(maxV, x); } for (int i = 1; i <= maxV; i++) { select[i] = nonSelect[i - 1] + sums[i]; nonSelect[i] = Math.max(select[i - 1], nonSelect[i - 1]); } return Math.max(select[maxV], nonSelect[maxV]); } }(code-box)

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; } };(code-box)

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 }(code-box)