Maximum Sum

Moderate
0/80
Average time to solve is 35m
3 upvotes
Asked in companies
DunzoAdobeArcesium

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
9
2 2 1 1 1 1 1 3 3
Sample Output 1 :
11
Explanation for Sample input 1 :
In the first step, we select one of the 3’s from the array and remove one occurrence of 3 and all occurrences of (3-1) and  (3+1) i.e 2 and 4. Now we left with {1, 1, 1, 1, 1, 3} elements in the array. 

Then again we select 3 in the next step and again 3 will be deleted and as (3-1) and (3+1) doesn't exist in the array so nothing more to be deleted in this step. Now we left with {1,1,1,1,1}. 

In the next five steps, we select 1 as the element and delete it. Thus the array becomes empty.

Thus the sum we got is 3+3+1+1+1+1+1 = 11 which is the maximum possible sum.
Sample Input 2 :
1
6
2 3 3 3 4 5
Sample Output 2 :
14
Hint

Think of brute force and try to generate all the possibilities to find the maximum sum

Approaches (3)
Recursion

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:

  1. Find the maximum number max in the array.
  2. 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.
  3. 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):

  1. If id reaches the end of freq array, return 0.
  2. Then we have two choices:
    1. id * freq[id] + maximumSumHelper(freq, id + 2)
    2. maximumSumHelper(freq, id + 1);
  3. Then return the maximum of both.
Time Complexity

O(2^MAX), where “MAX” is the maximum element present and N is the size of the array.

 

In the worst case, we will find the maximum element in an array that takes O(N) time. For every index of the freq array, we have two choices i.e either to include that element or exclude the element. Thus the overall running time will be O(2^MAX + N).   

Space Complexity

O(MAX), where “MAX” is the maximum element present in the array.

 

In the worst case, extra space is required to create the auxiliary array of size MAX, and also for the recursion stack.

Code Solution
(100% EXP penalty)
Maximum Sum
Full screen
Console