Last Updated: 30 Sep, 2021
Delete And Score
Moderate
Asked in company
You are given an integer array ‘arr’ of size ‘N’. You need to perform the following operation any number of times.
1- Select a element arr[i] and add it to your score.
2- Delete every element equal to arr[i] - 1 and arr[i] + 1.
Your task is to return the maximum possible score.
For example:
You are given arr = {5, 6, 7, 8}. Then our answer will be 14.
First select arr[1] = 6 and add it to your score. Score will be 6. Now, we also have to delete all elements equal to arr[1] - 1 = 5 and arr[i] + 1 = 7.
In next move select arr[3] = 8. Delete it and add it to your score. Score = 14. Now, no element is left to be deleted.
So, our final score is 14, which is the correct answer.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases.
The first line of each test case contains an integer, ‘N’, denoting the size of the array.
The second contains ‘N’ space-separated integers representing the elements of the array ‘arr’.
Output Format:
For each test case, print a single integer, denoting the maximum score possible after performing the operation any number of times.
The output of each test case will be printed in a separate line.
Constraints:
1 <= T <= 10
1 <= N <= 10 ^ 6
1 <= arr[i] <= 10 ^ 4
Time limit: 1 sec
Note:
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Approaches
First, we will create a count array, where count[i] stores (total occurrences of i in arr). We can add all the occurrences of an element to our score because we only have to delete that particular element and all occurrences of (element - 1) and (element + 1). We have two choices for every element in count: to include this element in our score or exclude it. If we include this element, we can not take the previous element (element - 1) but can take (element - 2). So, we will select the choice at every move that will add maximum value to our score.
Algorithm:
- Initialize a variable maxN with a value 10001
- Initialize an integer array count of size maxN
- For each element, num in arr
- Increment count[num] by 1
- return helper(maxN - 1, count)
- Maintain a function helper(int num, int[] count)
- If num is less than or equal to 0
- return 0
- Otherwise return maximum of (helper(num - 2, count) + (count[num] * num)) and helper(num - 1, count)
This approach is similar to Approach 1. If we create a recursive tree of Approach 1 we can see that we did a lot of repeated work. To avoid that in this approach, we will use an array memo to store already computed values, so we don’t have to compute them again.
Algorithm:
- Intialize a variable maxN with value 10001
- Initialize an integer array count of size maxN
- For each element, num in arr
- count[num]++
- Create an array memo of size maxN with the value -1 at all positions
- Return helper(maxN - 1, count, memo)
- Maintain a function helper(int num, int[] count, int[] memo)
- If num is less than or equal to 0
- return 0
- If memo[num] is not equal to -1
- return memo[num]
- Otherwise memo[num] = maximum of (helper(num - 2, count, memo) + (count[num] * num)) and helper(num - 1, count, memo)
- return memo[num]
This approach is similar to Approach 2. In this approach, we will create a dp array where dp[i] stores (i * total occurrences of i in arr) and will follow an iterative bottom-up approach.
Algorithm:
- Intialize a global variable maxN with value 10001
- Initialise an integer array dp of size maxN
- Iterate i in 0 to arr.length
- dp[arr[i]] += arr[i]
- Iterate i in 2 to maxN
- dp[i] = maximum of dp[i - 1] and dp[i - 2] + dp[i]
- Finally, return dp[maxN - 1].