-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0740 [M] Delete and Earn
Code with Senpai edited this page Jan 25, 2022
·
4 revisions
same idea as house robber
we can simplify the problem by storing number counts then it reduces to house robber where instead of checking adjacent we check -1
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
count = Counter(nums)
nums = sorted(list(set(nums)))
earn1, earn2 = 0, 0
for i in range(len(nums)):
curEarn = nums[i] * count[nums[i]]
if i > 0 and nums[i] == nums[i-1] + 1:
temp = earn2
earn2 = max(curEarn + earn1, earn2)
earn1 = temp
else:
temp = earn2
earn2 = curEarn + earn2
earn1 = temp
return earn2
class Solution(object):
def deleteAndEarn(self, nums):
points, prev, curr = collections.Counter(nums), 0, 0
for value in range(10001):
prev, curr = curr, max(prev + value * points[value], curr)
return curr
footer