Leetcode 740. Delete and Earn

문제

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.

배열이 주어질때 주어진 규칙대로 숫자들을 가져와 합한 최대값을 구하라

• 배열에서 값 하나를 가져와 결과에 더하면 가져온 값 i에 대해 모든 배열의 i-1과 i+1값을 없앤다.

예시

Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- 3을 가져오면 3 두개밖에 더 남지 않아 3 + 3 + 3 = 9 가 최대가 된다.

제한

• $1 <= nums.length <= 2 * 10^4$
• $1 <= nums[i] <= 10^4$

풀이법

1. 먼저 배열의 최대값 + 1 인 배열을 하나 만든다.
2. 만들어진 배열의 index 는 저장된 값, index에 해당하는 값은 그 값이 누적된 결과를 저장한다.
3. 같은 사이즈의 dp배열을 만들고, dp에는 여기까지 값을 구했을때 합의 최대값을 저장한다.
4. 경우의 수는 두개이다.
   4-1. 자신보다 1 적은 수를 구한다. - 그대로 가져오면 된다.
   4-2. 자신보다 2 적은 수를 구한다. - 결과에 자신의 누적합을 더하면 된다.

• 두 경우의 수중 최대가 되는것을 가져오면 된다.

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

        maximum = max(nums)

        if maximum == 0:
            return 0

        acc = [0] * (maximum + 1)

        for num in nums:
            acc[num] += num

        dp = [0] * (maximum + 1)

        dp[0] = 0
        dp[1] = acc[1]

        for i in range(2, maximum + 1):
            dp[i] = max(
                dp[i-2] + acc[i],
                dp[i-1]
            )

        return dp[-1]