Skip to content

740. Delete and Earn

MediumLeetCode

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