<p>You are given an integer array <code>nums</code>. You want to maximize the number of points you get by performing the following operation any number of times:</p>

<ul>
	<li>Pick any <code>nums[i]</code> and delete it to earn <code>nums[i]</code> points. Afterwards, you must delete <b>every</b> element equal to <code>nums[i] - 1</code> and <strong>every</strong> element equal to <code>nums[i] + 1</code>.</li>
</ul>

<p>Return <em>the <strong>maximum number of points</strong> you can earn by applying the above operation some number of times</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,4,2]
<strong>Output:</strong> 6
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,2,3,3,3,4]
<strong>Output:</strong> 9
<strong>Explanation:</strong> You can perform the following operations:
- Delete a 3 to earn 3 points. All 2&#39;s and 4&#39;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.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        nums_by_count = dict()
        for num in nums:
            if num in nums_by_count:
                nums_by_count[num] += 1
            else:
                nums_by_count[num] = 1
        nums_by_count = sorted(nums_by_count.items())
        total_with = 0
        total_without = 0
        prev = -1
        for num, occurrences in nums_by_count:
            prev_total_with = total_with
            prev_total_without = total_without
            if prev == num - 1:
                total_with = prev_total_without + (num * occurrences)
            else:
                total_with = max(prev_total_without, prev_total_with) + (num * occurrences)
            total_without = max(prev_total_without, prev_total_with)
            prev = num
        return max(total_with, total_without)




        # nums_by_count = dict()
        # for num in nums:
        #     if num in nums_by_count:
        #         nums_by_count[num] += 1
        #     else:
        #         nums_by_count[num] = 1
        # # print(sorted(nums))
        # # print(sorted(nums_by_count.items()))
        # memo = dict()
        # def memoized(nums: Dict[int, int]) -> int:
        #     if frozenset(nums) in memo:
        #         # print(nums, "already memoized")
        #         return memo[frozenset(nums)]
        #     if len(nums) == 0:
        #         return 0
        #     max_found = 0
        #     for points, occurrences in nums.items():
        #         next_nums = nums.copy()
        #         # if occurrences > 1:
        #         # if (updated_occurrences := occurrences - 1) > 0:
        #         #     next_nums[points] = updated_occurrences
        #         # else:
        #         del next_nums[points]
        #         if points + 1 in next_nums:
        #             del next_nums[points + 1]
        #         if points - 1 in next_nums:
        #             del next_nums[points - 1]
        #         points *= occurrences
        #         if (total := points + memoized(next_nums)) > max_found:
        #             memo[frozenset(nums)] = total
        #             max_found = total
        #             # print(nums, max_found)
        #     return max_found
        #     # return memo[frozenset(nums)]
        # return memoized(nums_by_count)
        # # return memoized(dict(sorted(nums_by_count.items())))



        # nums_by_count = dict()
        # for num in nums:
        #     if num in nums_by_count:
        #         nums_by_count[num] += 1
        #     else:
        #         nums_by_count[num] = 1
        # memo = dict()
        # def memoized(nums: Dict[int,int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     if frozenset(nums) in memo:
        #         print(nums, "already memoized")
        #         return memo[frozenset(nums)]
        #     routes = []
        #     max_found = 0
        #     for i in range(len(nums)):
        #         points = nums[i]
        #         next_nums = nums.copy()
        #         del next_nums[points]
        #         if points + 1 in next_nums:
        #             del next_nums[points + 1]
        #         if points - 1 in next_nums:
        #             del next_nums[points - 1]
        #         memoized(next_nums)

        #         if (total := points + memoized(next_nums)) > max_found:
        #             memo[frozenset(nums)] = total
        #     return max_found
        # return memoized(nums_by_count)


        # memo = dict()
        # def memoized(nums: Set[int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     if frozenset(nums) in memo:
        #         return memo[frozenset(nums)]
        #     max_found = 0
        #     for points in nums:
        #         next_nums = nums.copy()
        #         next_nums.discard(points)
        #         next_nums.discard(points + 1)
        #         next_nums.discard(points - 1)
        #         if (total := points + memoized(next_nums)) > max_found:
        #             memo[frozenset(nums)] = total
        #             max_found = total
        #     return memo[frozenset(nums)]
        # return memoized(set(nums))


        # memo = dict()
        # def memoized(nums: Set[int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     if frozenset(nums) in memo:
        #         print(nums, "already memoized")
        #         return memo[frozenset(nums)]
        #     routes = []
        #     max_found = 0
        #     for points in nums:
        #         next_nums = nums.copy()
        #         next_nums.discard(points)
        #         next_nums.discard(points + 1)
        #         next_nums.discard(points - 1)
        #         memoized(next_nums)

        #         if (total := points + memoized(next_nums)) > max_found:
        #             memo[frozenset(nums)] = total
        #     return memo[frozenset(nums)]
        # return memoized(set(nums))


        # memo = dict()
        # def memoized(nums: Set[int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     if frozenset(nums) in memo:
        #         return memo[frozenset(nums)]
        #     max_found = 0
        #     for points in nums:
        #         next_nums = nums.copy()
        #         next_nums.discard(points)
        #         next_nums.discard(points + 1)
        #         next_nums.discard(points - 1)
        #         memo[frozenset(nums)] = points + memoized(next_nums)
        #     return memo[frozenset(nums)]
        # return memoized(set(nums))


        # memo = dict()
        # def memoized(nums: Set[int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     if frozenset(nums) in memo:
        #         return memo[frozenset(nums)]
        #     max_found = 0
        #     for points in nums:
        #         next_nums = nums.copy()
        #         next_nums.discard(points)
        #         next_nums.discard(points + 1)
        #         next_nums.discard(points - 1)
        #         if (total := points + memoized(next_nums)) > max_found:
        #             memo[frozenset(nums)] = total
        #     return max_found
        # return memoized(set(nums))



        # memo = dict()
        # def memoized(nums: Set[int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     if frozenset(nums) in memo:
        #         return memo[frozenset(nums)]
        #     max_found = 0
        #     for points in nums:
        #         next_nums = nums.copy()
        #         next_nums.discard(points)
        #         next_nums.discard(points + 1)
        #         next_nums.discard(points - 1)
        #         if next_nums := frozenset(next_nums) not in memo and (total := points + memoized(next_nums)) > max_found:
        #             memo[frozenset(nums)] = total
        #             max_found = total
        #     return max_found
        # return memoized(set(nums))





        # memo = dict()
        # def memoized(nums: Set[int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     if frozenset(nums) in memo:
        #         return memo[frozenset(nums)]
        #     max_found = 0
        #     for points in nums:
        #         next_nums = nums.copy()
        #         next_nums.discard(points)
        #         next_nums.discard(points + 1)
        #         next_nums.discard(points - 1)
        #         if next_nums := frozenset(next_nums) not in memo and (total := points + memoized(next_nums)) > max_found:
        #             memo[frozenset(nums)] = total
        #             max_found = total
        #     return max_found
        # return memoized(set(nums))


        # memo = dict()
        # def memoized(nums: Set[int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     if frozenset(nums) in memo:
        #         return memo[frozenset(nums)]
        #     max_found = 0
        #     for points in nums:
        #         next_nums = nums.copy()
        #         next_nums.discard(points)
        #         next_nums.discard(points + 1)
        #         next_nums.discard(points - 1)
        #         if (total := points + memoized(next_nums)) > max_found:
        #             memo[frozenset(nums)] = total
        #             max_found = total
        #     return max_found
        # return memoized(set(nums))




        # seen = set()
        # def memoized(nums: Set[int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     # if frozenset(nums) in seen:
        #     #     return memo[frozenset(nums)]
        #     max_found = 0
        #     for points in nums:
        #         next_nums = nums.copy()
        #         next_nums.discard(points)
        #         next_nums.discard(points + 1)
        #         next_nums.discard(points - 1)
        #         if next_nums := frozenset(next_nums) not in seen and (total := points + memoized(next_nums)) > max_found:
        #             # memo[frozenset(nums)] = total
        #             seen.add(next_nums)
        #             max_found = total
        #     return max_found
        # return memoized(set(nums))



        # def memoized(nums: Set[int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     max_found = 0
        #     for points in nums:
        #         next_nums = nums.copy()
        #         next_nums.discard(points)
        #         next_nums.discard(points + 1)
        #         next_nums.discard(points - 1)
        #         if (total := points + memoized(next_nums)) > max_found:
        #             max_found = total
        #     return max_found
        # return memoized(set(nums))




        # memo = dict()
        # def memoized(nums: Set[int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     if frozenset(nums) in memo:
        #         return memo[frozenset(nums)]
        #     max_found = 0
        #     for points in nums:
        #         next_nums = nums.copy()
        #         next_nums.discard(points)
        #         next_nums.discard(points + 1)
        #         next_nums.discard(points - 1)
        #         memoized(next_nums)
        #         if (total := points + memoized(next_nums)) > max_found:
        #             memo[frozenset(nums)] = total
        #             max_found = total
        #     return max_found
        # return memoized(set(nums))




        # memo = dict()
        # def memoized(nums: Set[int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     if frozenset(nums) in memo:
        #         # print(nums, "already memoized")
        #         return memo[frozenset(nums)]
        #     routes = []
        #     max_found = 0
        #     for points in nums:
        #         next_nums = nums.copy()
        #         next_nums.discard(points)
        #         next_nums.discard(points + 1)
        #         next_nums.discard(points - 1)
        #         memoized(next_nums)

        #         if (total := points + memoized(next_nums)) > max_found:
        #             memo[frozenset(nums)] = total
        #     return max_found
        # return memoized(set(nums))




        # nums_by_count = dict()
        # for num in nums:
        #     if num in nums_by_count:
        #         nums_by_count[num] += 1
        #     else:
        #         nums_by_count[num] = 1
        # memo = dict()
        # def memoized(nums: Dict[int, int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     if frozenset(nums) in memo:
        #         # print(nums, "already memoized")
        #         return memo[frozenset(nums)]
        #     routes = []
        #     max_found = 0
        #     for points in nums.keys():
        #         # points = nums[i]
        #         next_nums = nums.copy()
        #         del next_nums[points]
        #         if points + 1 in next_nums:
        #             del next_nums[points + 1]
        #         if points - 1 in next_nums:
        #             del next_nums[points - 1]
        #         memoized(next_nums)

        #         if (total := points + memoized(next_nums)) > max_found:
        #             memo[frozenset(nums)] = total
        #     return max_found
        # return memoized(nums_by_count)



        # indices = dict()
        # for index in range(len(nums)):
        #     points = nums[index]
        #     if indices.get(points):
        #         indices[points].append(index)
        #     else:
        #         indices[points] = [index]
        #     print(indices)

        # earnings = []
        # memo = dict()
        # for i in range(len(nums)):
        #     deleted = nums[:i] + nums[i + 1:]
        #     if memo[tuple(deleted)]:
        #         earnings.append(nums[i])
        #     else:
        #         points = nums[i]
        #         for index in indices[points - 1]:
        #             deleted = 
        #     memo[ns]
        #     print(ns)
        # return 0

        # for each arrangement of nums, either:
        # calculate the value as nums[i] + deleteAndEarn(nums), but with nums modified
        # find the memoized arrangement and add that instead.
        # represent each arrangement of nums as a tuple


        # memo = dict()
        # def memoized(nums: List[int]) -> int:
        #     if len(nums) == 0:
        #         return 0
        #     if tuple(nums) in memo:
        #         # print(nums, "already memoized")
        #         return memo[tuple(nums)]
        #     # maximum = 0
        #     routes = []
        #     for i in range(len(nums)):
        #         points = nums[i]
        #         next_nums = nums.copy()
        #         del next_nums[i]
        #         j = 0
        #         while j < len(next_nums):
        #             if next_nums[j] == points - 1 or next_nums[j] == points + 1:
        #                 del next_nums[j]
        #             else:
        #                 j += 1
        #         # routes.append(next_nums)
        #         if tuple(next_nums) not in memo:
        #             memoized(next_nums)
        #         # routes.append(points + memoized(next_nums))
        #     # if tuple(nums) in memo:
        #     #     print("rememoizing", nums)

        #     memo[tuple(nums)] = max(routes)

        #         #     memo[tuple(nums)] = max(memo[tuple(nums)], points + memoized(next_nums))
        #         # else:
        #         #     memo[tuple(nums)] = points + memoized(next_nums)
        #     return memo[tuple(nums)]
        # return memoized(nums)
18611