Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points.  After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points.  Return the maximum number of points you can earn by applying such operations.


Example 1:

Input: nums = [3, 4, 2]
Output: 6
Explanation: 
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.



Example 2:

Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: 
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.



Note:
The length of nums is at most 20000.
Each element nums[i] is an integer in the range [1, 10000].

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Starter code: class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        

Solutions:
class Solution:

	def deleteAndEarn(self, nums):
		count = collections.Counter(nums)
		prev = None
		avoid = using = 0
		for k in sorted(count):
			temp = max(avoid, using)
			if k - 1 != prev:
				using = k * count[k] + temp
				avoid = temp
			else:
				using = k * count[k] + avoid
				avoid = temp
			prev = k
		return max(avoid, using)


class Solution:

	def deleteAndEarn(self, nums):
		if nums == []:
			return 0
		if len(nums) == 1:
			return nums[0]
		nums.sort()
		numsp = nums[0]
		choose = [0, nums[0]]
		for i in range(1, len(nums)):
			numsc = nums[i]
			if numsc == numsp:
				choose[1] += numsc
				continue
			elif numsc == numsp + 1:
				temp = choose[0]
				choose[0] = max(choose)
				choose[1] = temp + numsc
				numsp = numsc
			else:
				choose[0] = max(choose)
				choose[1] = choose[0] + numsc
				numsp = numsc
		return max(choose)


class Solution:

	def deleteAndEarn(self, nums):
		nums.sort()
		nums.append(-1)
		(prev_max, cur_max) = (0, 0)
		prev = -1
		(j, i) = (0, 0)
		while i < len(nums):
			if nums[i] == nums[j]:
				i += 1
				continue
			dif = i - j
			temp = dif * nums[j]
			if nums[j] == prev + 1:
				(prev_max, cur_max) = (cur_max, max(temp + prev_max, cur_max))
			else:
				(prev_max, cur_max) = (cur_max, temp + cur_max)
			prev = nums[j]
			j = i
			i += 1
		return cur_max


class Solution:

	def deleteAndEarn(self, nums):
		if len(nums) == 0:
			return 0
		upper = max(nums)
		ordered = [0] * (upper + 1)
		for i in nums:
			ordered[i] += i
		ans = [0] * (upper + 1)
		ans[1] = ordered[1]
		for i in range(2, upper + 1):
			ans[i] = max(ans[i - 1], ans[i - 2] + ordered[i])
		return ans[upper]


class Solution:

	def deleteAndEarn(self, nums):
		from collections import Counter
		c = Counter(nums)
		n = len(nums)
		pick = {-math.inf: 0}
		miss = {-math.inf: 0}
		prev = -math.inf
		for (num, freq) in sorted(c.items()):
			if prev == num - 1:
				pick[num] = miss[num - 1] + num * freq
				miss[num] = max(miss[num - 1], pick[num - 1])
			else:
				pick[num] = max(miss[prev], pick[prev]) + num * freq
				miss[num] = max(miss[prev], pick[prev])
			prev = num
		return max(pick[prev], miss[prev])


class Solution:

	def deleteAndEarn(self, nums):
		if len(nums) == 0:
			return 0
		nums.sort()
		a = [0] * len(nums)
		b = [0] * len(nums)
		k = -1
		a[-1] = nums[-1]
		b[-1] = 0
		for i in range(len(nums) - 2, -1, -1):
			print(nums[i], nums[i + 1])
			if nums[i] == nums[i + 1] - 1:
				a[i] = max(a[k], b[k]) + nums[i] if k != -1 else nums[i]
				b[i] = max(a[i + 1], b[i + 1])
			elif nums[i] == nums[i + 1]:
				a[i] = a[i + 1] + nums[i]
				b[i] = b[i + 1]
			else:
				a[i] = max(a[i + 1], b[i + 1]) + nums[i]
				b[i] = max(a[i + 1], b[i + 1])
			if nums[i] < nums[i + 1]:
				k = i + 1
		return max(a[0], b[0])


class Solution:

	def deleteAndEarn(self, nums):
		if len(nums) == 0:
			return 0
		nums.sort()
		count = collections.Counter(nums)
		take = [0] * (1 + nums[-1])
		delete = [0] * (1 + nums[-1])
		try:
			take[1] = count[1]
		except KeyError:
			take[1] = 0
		for i in range(2, nums[-1] + 1):
			print(i)
			try:
				delete[i] = max(take[i - 1], delete[i - 1])
				take[i] = i * count[i] + max(take[i - 2], delete[i - 1])
			except KeyError:
				continue
		print(take)
		print(delete)
		res = max(take[-1], delete[-1])
		return res