Leetcode # 740. Delete and Earn

https://leetcode.com/problems/delete-and-earn

Solution

Time Complexity: O(len(nums))
Space Complexity: O(len(counter))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def deleteAndEarn(self, nums: List[int]) -> int:
    counter = collections.Counter(nums)
    dp = [0, 0] # don't take or take
    _nums = sorted(counter)
    for i, num in enumerate(_nums):
      take = num * counter[num] \
              + (max(dp) if _nums[i - 1] != num - 1 \
             else dp[0])
      dp = [max(dp), take]
    return max(dp)

Last Updated on 2023/08/16 by A1go