Delete and Earn — LeetCode 740 Python Solution

The problem

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.

Example

Input

nums = [3,4,2]

Output

6

Explanation

You can perform the following operations:

Python solution

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        mx = -inf
        for num in nums:
            mx = max(mx, num)
        total = [0] * (mx + 1)
        for num in nums:
            total[num] += num
        first = total[0]
        second = max(total[0], total[1])
        for i in range(2, mx + 1):
            cur = max(first + total[i], second)
            first = second
            second = cur
        return second

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 740. Delete and Earn is filed here because LeetCode tags it Dynamic Programming, which is the vocabulary this hub collects.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems