740. Delete And Earn - Explanation

1. Recursion

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

        def dfs(i):
            if i >= len(nums):
                return 0

            cur = nums[i]
            pick = 0
            while i < len(nums) and nums[i] == cur:
                pick += nums[i]
                i += 1

            res = dfs(i)
            while i < len(nums) and nums[i] == 1 + cur:
                i += 1

            res = max(res, pick + dfs(i))
            return res

        return dfs(0)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$

2. Dynamic Programming (Top-Down)

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        val = defaultdict(int)
        for num in nums:
            val[num] += num
        nums = sorted(list(set(nums)))
        memo = [-1] * len(nums)

        def dfs(i):
            if i >= len(nums):
                return 0
            if memo[i] != -1:
                return memo[i]

            res = val[nums[i]]
            if i + 1 < len(nums) and nums[i] + 1 == nums[i + 1]:
                res += dfs(i + 2)
            else:
                res += dfs(i + 1)

            res = max(res, dfs(i + 1))
            memo[i] = res
            return res

        return dfs(0)

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up) - I

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        val = defaultdict(int)
        for num in nums:
            val[num] += num
        nums = sorted(list(set(nums)))

        dp = [0] * (len(nums) + 1)
        for i in range(len(nums) - 1, -1, -1):
            take = val[nums[i]]
            if i + 1 < len(nums) and nums[i + 1] == nums[i] + 1:
                take += dp[i + 2]
            else:
                take += dp[i + 1]
            dp[i] = max(dp[i + 1], take)

        return dp[0]

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

4. Dynamic Programming (Bottom-Up) - II

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        m = max(nums)
        dp = [0] * (m + 2)

        for num in nums:
            dp[num] += num
        for i in range(m - 1, 0, -1):
            dp[i] = max(dp[i + 1], dp[i + 2] + dp[i])

        return dp[1]

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(m)$

Where $m$ is the maximum element in the array and $n$ is the size of the array.

5. Dynamic Programming (Space Optimized)

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

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$