[leetcode #740] Delete and Earn

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. 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⁴
・ 1 <= nums[i] <= 10⁴

Idea

전형적인 dp문제다. 어떤 특정한 수를 합에 더할 때 해당수의 ±1인 수들을 다 지웠을 때 최대가 되는 합을 구하면 된다.

수의 범위가 10⁴보다 작거나 같으므로 sum의 범위를 10⁴로 제한하여 만든다. 주어진 배열을 탐색하여 해당 수를 전부 합한다. 이 때 sum의 index는 배열의 수, value는 해당 수의 전체 합이 된다.

각 값의 전체 합을 계산한 뒤 dp를 만든다. dp는 2d array로 첫 번째 index는 배열에서의 값, 두 번째 index는 해당 값에서의 최대값을 의미한다. 두 번째 index가 0일 때는 해당 값이 제거되었을 때의 최대값, 1일 때는 해당 값이 제거되지 않았을 때의 최대값이다.

sum을 하나씩 조사하면서 0인 경우 (해당 값이 배열에 없을 경우), dp 0번째, 1번째 모두를 전부 이전 index의 최대값으로 설정한다.

sum이 0이 아닌 경우 해당 값이 제거되었을 때의 최대값은
1. 현재 sum과 이전 dp에서 이전 값이 제거되지 않을 때 최대값의 합
2. 이전 dp에서 이전 값이 제거되었을 때의 최대값
중 더 큰 값으로 설정한다.

해당 값이 제거되지 않았을 때의 최대값은 이전 dp에서 이전 값이 제거되었을 때의 최대값과 동일하다.

모든 과정을 반복한 뒤 dp의 최종 index 값 중 더 큰 값을 리턴하면 된다.

Solution

class Solution {
    public int deleteAndEarn(int[] nums) {
        int[] sum = new int[10_000+1];
        int max = 0;

        for (int i=0; i < nums.length; i++) {
            sum[nums[i]] += nums[i];
            max = Math.max(max, nums[i]);
        }

        int res = 0;
        int[][] dp = new int[max+1][2]; // 0 - removed, 1 - not removed

        for (int i=1; i <= max; i++) {
            if (sum[i] == 0) {
                int maxValue = Math.max(dp[i-1][0], dp[i-1][1]);
                dp[i][0] = maxValue;
                dp[i][1] = maxValue;

                continue;
            }
            dp[i][0] = Math.max(sum[i] + dp[i-1][1], dp[i-1][0]);
            dp[i][1] = dp[i-1][0];
        }

        return Math.max(dp[max][0], dp[max][1]);
    }
}

Reference

https://leetcode.com/problems/delete-and-earn/