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
- code TLE
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
count = Counter(nums)
uniq = list(count.keys())
# @lru_cache can't hash a list
def dfs(nums):
if not nums:
return 0
res = 0
for v in nums:
res = max(res, v * count[v] + dfs(list(filter(lambda x: x != v - 1 and x!= v and x != v + 1, nums))))
return res
return dfs(uniq)
- code
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
count = Counter(nums) # value, count
uniq = sorted(count) # 2,3,4 values
dp = [0] * len(count)
dp[0] = uniq[0] * count[uniq[0]]
if len(uniq) == 1: return dp[0]
if uniq[1] == uniq[0] + 1:
dp[1] = max(dp[0], uniq[1] * count[uniq[1]])
else: dp[1] = dp[0] + uniq[1] * count[uniq[1]]
for i in range(2, len(uniq)):
if uniq[i] == uniq[i-1] + 1:
dp[i] = max(dp[i-2] + uniq[i]*count[uniq[i]] , dp[i-1])
else:
dp[i] = dp[i-1] + uniq[i] * count[uniq[i]]
return dp[-1]
- code
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
count = Counter(nums) # value, count
last = -1 # check if v is next to last value
two_step_before = one_step_before = cur = 0 # result so far
for v in sorted(count):
if v == last + 1:
cur = max(two_step_before + v * count[v] , one_step_before)
else:
cur = one_step_before + v * count[v]
two_step_before, one_step_before, last = one_step_before, cur, v
return cur