[LeetCode] 740. Delete and Earn - 문제풀이

Description

주어진 배열에서 아래 작업을 여러 번 수행하여 얻는 최대 점수를 반환하는 문제입니다.

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.

Example 1:

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

Example 2:

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

Constraints:

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

Solution 1. Dynamic Programming

public int deleteAndEarn(int[] nums) {

    int[] values = new int[10001];
    for (int num : nums) {
        values[num] += num;
    }
    int take = 0, skip = 0;
    for (int value : values) {
        int temp = Math.max(skip + value, take);
        skip = take;
        take = temp;
    }
    return take;
}

먼저 각 요소값별 중복값을 더한 sum을 계산해 해쉬테이블에 넣어줍니다. 그리고 동적 프로그래밍을 이용해 현재값에서 올 수 있는 최대값은 현재값+이전요소까지의 최대값이거나 직전까지의 최대값중 큰값입니다.

Reference

Delete and Earn - LeetCode