## Saturday, April 28, 2018

### LeetCode 740 - Delete and Earn

https://leetcode.com/problems/delete-and-earn/description/
Given an array nums of integers, you can perform operations on the array.
In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.
You start with 0 points. Return the maximum number of points you can earn by applying such operations.
Example 1:
Input: nums = [3, 4, 2]
Output: 6
Explanation:
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.

Example 2:
Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation:
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.

Note:
• The length of nums is at most 20000.
• Each element nums[i] is an integer in the range [1, 10000].
• Because all numbers are positive, if we "take" a number (use it to score points), we might as well take all copies of it, since we've already erased all its neighbors. We could keep a count of each number so we know how many points taking a number is worth total.
Now let's investigate what happens when we add a new number X (plus copies) that is larger than all previous numbers. Naively, our answer would be the previous answer, plus the value of X - which can be solved with dynamic programming. However, this fails if our previous answer had a number taken that was adjacent to X.
Luckily, we can remedy this. Let's say we knew using, the value of our previous answer, and avoid, the value of our previous answer that doesn't use the previously largest value prev. Then we could compute new values of using and avoid appropriately.
Algorithm
For each unique value k of nums in increasing order, let's maintain the correct values of avoid and using, which represent the answer if we don't take or take k respectively.
If the new value k is adjacent to the previously largest value prev, then the answer if we must take k is (the point value of k) + avoid, while the answer if we must not take k is max(avoid, using). Similarly, if kis not adjacent to prev, the answer if we must take k is (the point value of k) + max(avoid, using), and the answer if we must not take k is max(avoid, using).
At the end, the best answer may or may not use the largest value in nums, so we return max(avoid, using).
Our demonstrated solutions showcase two different kinds of sorts: a library one, and a radix sort. For each language, the other kind of solution can be done without much difficulty, by using an array (Python) or HashMap (Java) respectively.
• Time Complexity (Python): $O(N \log N)$, where $N$ is the length of nums. We make a single pass through the sorted keys of $N$, and the complexity is dominated by the sorting step.
• Space Complexity (Python): $O(N)$, the size of our count.
• Time Complexity (Java): We performed a radix sort instead, so our complexity is $O(N+W)$ where $W$ is the range of allowable values for nums[i].
• Space Complexity (Java): $O(W)$, the size of our count.
https://leetcode.com/problems/delete-and-earn/discuss/109895/JavaC++-Clean-Code-with-Explanation
1. If we sort all the numbers into buckets indexed by these numbers, this is essentially asking you to repetitively take an bucket while giving up the 2 buckets next to it. (the range of these numbers is [1, 10000])
2. The optimal final result can be derived by keep updating 2 variables skip_itake_i, which stands for:
skip_i : the best result for sub-problem of first (i+1) buckets from 0 to i, while you skip the ith bucket.
take_i : the best result for sub-problem of first (i+1) buckets from 0 to i, while you take the ith bucket.
3. DP formula:
take[i] = skip[i-1] + values[i];
skip[i] = Math.max(skip[i-1], take[i-1]);
take[i] can only be derived from: if you skipped the [i-1]th bucket, and you take bucket[i].
skip[i] through, can be derived from either take[i-1] or skip[i-1], whatever the bigger;
 * for numbers from [1 - 10000], each has a total sum sums[i]; if you earn sums[i], you cannot earn sums[i-1] and sums[i+1]
* kind of like house robbing. you cannot rob 2 connected houses.
    public int deleteAndEarn(int[] nums) {
int n = 10001;
int[] values = new int[n];
for (int num : nums)
values[num] += num;

int take = 0, skip = 0;
for (int i = 0; i < n; i++) {
int takei = skip + values[i];
int skipi = Math.max(skip, take);
take = takei;
skip = skipi;
}
return Math.max(take, skip);
}

https://leetcode.com/problems/delete-and-earn/discuss/109871/Awesome-Python-4-liner-with-explanation-Reduce-to-House-Robbers-Question
The condition that we cannot pick adjacent values is similar to the House Robber question that we cannot rob adjacent houses. Simply pass points into the robfunction for a quick win

https://leetcode.com/problems/delete-and-earn/discuss/109889/Java-Easy-DP-Solution
Time: O(M+N)
Space: O(N)
M: the length of input array
N: the range of the value of each int element

public int deleteAndEarn(int[] nums) {
int[] count = new int[10001];
for(int n : nums){
count[n] += n;
}
int[] dp = new int[10003];
for(int i = 10000; i >= 0; i--) {
dp[i] = Math.max(count[i] + dp[i + 2], dp[i + 1]);
}
return dp[0];
}

public int deleteAndEarn(int[] nums) {
int[] count = new int[10001];
for (int x: nums) count[x]++;
int avoid = 0, using = 0, prev = -1;

for (int k = 0; k <= 10000; ++k) if (count[k] > 0) {
int m = Math.max(avoid, using);
if (k - 1 != prev) {
using = k * count[k] + m;
avoid = m;
} else {
using = k * count[k] + avoid;
avoid = m;
}
prev = k;
}
return Math.max(avoid, using);
}
class Solution(object):
def deleteAndEarn(self, nums):
count = collections.Counter(nums)
prev = None
avoid = using = 0
for k in sorted(count):
if k - 1 != prev:
avoid, using = max(avoid, using), k * count[k] + max(avoid, using)
else:
avoid, using = max(avoid, using), k * count[k] + avoid
prev = k
return max(avoid, using)