Last Updated: 22 Oct, 2020
Maximum Sum
Moderate
Asked in companies
You are given an array “ARR” of N integers. You are required to perform an operation on the array each time until it becomes empty. The operation is to select an element from the array(let’s say at ith index i.e ARR[i]) and remove one occurrence of the selected element from the array and remove all the occurrences of (ARR[i]-1) and (ARR[i]+1) from the array(if present). Your task is to maximize the sum of selected elements from the array.
For example, let’s say the given array is [2, 3, 3, 3, 4, 5].
The maximum possible sum for the given array would be 14. Because if we select one of the 3’s from the array, then one 3 and all occurrences of (3-1) and (3+1) i.e 2 and 4 will be deleted from the array. Now we left with {3,3,5} elements in the array. Then again we select 3 in the next two steps and in both steps 3 will be deleted also (3-1) and (3+1) doesn't exist in the array so nothing extra to delete in both steps. Now we left with only {5} and in the next step, we select the 5 and delete it. Then the array becomes empty. Thus the sum of selected elements will be 3+3+3+5 = 14.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases or queries to be processed.
Then the test case follows.
The first line of each test case contains integer N, denoting the size of the array.
The second line of each test case contains 'N' single space-separated integers representing the array elements.
Output Format :
For each test case, print a single integer denoting the maximum sum, in a single line.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= ARR[i] <= 10^5
Where 'ARR[i]' denotes the 'ith' element of the array.
Time Limit: 1 sec
Approaches
The key point to notice here is that in the given problem that we don’t need to delete anything from the array while selecting arr[i] from the array. We just only care about whether we select any number arr[i] from the array then we cant select the arr[i]+1 and arr[i]-1 from the array to maximize the sum in the next steps. So we will find the maximum number max in the array and create a new auxiliary array of the size max+1 that stores the number of occurrences of each unique element in the array. The count is stored in an auxiliary array at their respective index.
Now the problem is to find the maximum sum of a subsequence of the array where the subsequence does not contain adjacent elements of the array. This problem is similar to the 0/1 Knapsack Problem in which in the recursion call at any index, we have two choices whether to include that element in sum or exclude that element. Now if we choose the current number to add to the sum then recur for index i+2 or If we don’t choose the current index then recur for index i+1 and this way we find the maximum sum.
Algorithm:
- Find the maximum number max in the array.
- Create a new auxiliary array freq of size max+1 and store frequencies of unique elements in the array, where freq[id] denotes the number of times ‘id’ as an element is present in the input array.
- Define and call a helper function, maximumSumHelper(freq[], id) to calculate the maximum possible sum where freq is the frequency array and id denotes the current index of this freq array and return maximumSumHelper(freq, 0).
long maximumSumHelper(freq[], id):
- If id reaches the end of freq array, return 0.
- Then we have two choices:
- id * freq[id] + maximumSumHelper(freq, id + 2)
- maximumSumHelper(freq, id + 1);
- Then return the maximum of both.
- The previous approach uses recursion which has many overlapping subproblems. i.e recursive function computes the same sub-problems again and again. So we can use memoization to overcome the overlapping subproblems.
- To reiterate memoization is when we store the results in a lookup array(dp) of all previously solved subproblems and use the results from the dp if we encounter the problem that has already been solved.
- Since there is only one state which is changing in the recursive function maximumSumHelper() i.e id So we use the 1-dimensional array dp[] to store all the subproblems. And dp[id] will store the maximum possible sum from the starting index till id index.
Algorithm:
- Find the maximum number max in the array.
- Create a new auxiliary array freq of size max+1 and store frequencies of unique elements in the array, where freq[id] denotes the number of times ‘id’ as an element is present in the input array.
- Define and call a helper function, maximumSumHelper(freq[], id, dp[]) to calculate the maximum possible sum where freq is the frequency array, id denotes the current index of this freq array and dp represents the lookup array and return maximumSumHelper(freq, 0, dp).
long maximumSumHelper(freq[], id, dp[]):
- If id reaches the end of freq array, return 0.
- If we already solve the same subproblem for index id, return dp[id].
- Otherwise we have two choices:
- id * ans[id] + maximumSumHelper(ans, id + 2)
- maximumSumHelper(ans, id + 1);
- Then store the maximum of both in dp[id] and return dp[id].
The idea is to use a bottom-up dynamic programming approach instead of a memoization approach. In this, we also have two choices whether to select or not. If we select then we take the occurrences of that number and the value stored at dp[i-2] as dp[i-1] will be deleted and not be taken to count. If we do not select the number then we take dp[i-1] which have been already calculated.
Algorithm:
- Find the maximum number max in the array.
- Create a new auxiliary array dp of size max+1 and store frequencies of unique elements in the array, where dp[i] denotes the number of times i as an element is present in the input array.
- Iterate the dp array(we will use this array to store the results), now for each index i from 2 to MAX we have two choices:
- dp[i] = max(dp[i-1], dp[i-2] + dp[i]*i).
- Return dp[MAX], which have the maximum sum of the selected numbers.