740. Delete and Earn
MediumLeetCodeYou 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
How to solve the problem
- Optimized Dynamic Programming
python
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
sum = [0] * (max(nums) + 1) # Store the total value for each unique number
for num in nums:
sum[num] += num # Accumulate total value for each number
def rob(nums): # Standard House Robber DP solution
f0 = f1 = 0
for num in nums:
f0, f1 = f1, max(f0 + num, f1)
return f1
return rob(sum) # Apply House Robber DP to the new array
Complexity
Time complexity: O(n) Space complexity: O(1)
Comments
No comments yet. Be the first to comment!