Given an array A[] having N positive integers, the task is to perform the following operations and maximize the sum obtained while reducing the array:
- Select an array element (say A[i]) and delete one occurrence of that element and add A[i] to the sum.
- Delete all the occurrences of A[i]-1 and A[i]+1.
- Perform these operations until the array is empty.
Examples:
Input: A[] = {3, 4, 2}
Output: 6
Explanation: First, delete number 4 to add 4 to sum and consequently 3 is also deleted.
After that the array A = [2].
Then we delete number 2 and add 2.
Array becomes empty i.e. array A = [].
And hence total sum = (4 + 2) = 6Input: A[] = {2, 2, 3, 3, 3, 4}
Output: 9
Explanation: First, delete number 3 to add 3. And all 2’s and 4’s numbers are also deleted.
After that we the array is A = [3, 3].
Then delete number 3 again to add 3 points. Sum = 3 + 3 = 6.
The array is now A = [3].
In last operation delete number 3 once again to add 3. Sum = 6+3 = 9.
Now array becomes empty.
Hence maximum sum obtained is 9.
Naive Approach: The naive approach is to try to reduce the array in all possible ways, i.e. for any value (say A[i] )that can be selected and one occurrence of that element can be deleted or any other element having difference of 1 with A[i] can be selected (if that is present in array) and one occurrence of that can be removed.
Time Complexity: O(2N)
Auxiliary Space: O(N)
Efficient Approach: This problem can be solved using Dynamic Programming based on the following idea:
If an element x is deleted once then all occurrences of x-1 and x+1 will be removed from array.
- So, if all array elements having value from 0 till x is considered then maximum sum till x depends on maximum sum till x-2 and maximum sum till x-1, i.e. if x is included then x-1 cannot be included and vice versa. [No need to consider the x+1 or x+2 because here iteration is from lower value to upper value side]
- Suppose these max values for each x are stored in an array (say dp[]) then dp[x] = max(dp[x-1], dp[x-2]+x*occurrences of x).
Follow the illustration below for a better understanding.
Illustration:
Consider an array A[] = {2, 2, 3, 3, 3, 4}
So the frequency of elements will be:
freq = {{2 -> 2}, {3 -> 3}, {4 -> 1}}Maximum of array is 4.
So the dp[] array will be of size 5.
The dp[] array will be {0, 0, 0, 0, 0}For x = 2:
=> dp[2] = max(dp[1], dp[0] + freq[2]*2)
= max(0, 2*2) = max(0, 0 + 4) = 4
=> dp[] = {0, 0, 4, 0, 0}For x = 3:
=> dp[3] = max(dp[2], dp[1] + freq[3]*3)
= max(4, 0 + 3*3) = max(0, 9) = 9
=> dp[] = {0, 0, 4, 9, 0}For x = 4:
=> dp[4] = max(dp[3], dp[2] + freq[4]*4)
= max(9, 4 + 4*1) = max(9, 8) = 9
=> dp[] = {0, 0, 4, 9, 9}So the answer is dp[4] = 9 which is the maximum possible sum
Follow the steps mentioned below to implement the above observation:
- Create an unordered_map mp to store the frequency of each array element.
- Calculate the maximum value of the array (say max_val).
- Create one array dp[] to store the maximum values as in the observation and initialize dp[1] as count of 1s.
- Iterate from i = 2 to max_val:
- Calculate the dp[i] as mentioned above.
- Return the dp[max_val] after all iterations as answer because it holds the maximum possible sum.
Below is the implementation of the above approach:
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// Function to return Maximum number// of points that can be earnedint MaximumPoints(int A[], int array_size){ // Maximum element in array A int element_max = *max_element(A, A + array_size); unordered_map<int, int> mp; // Dp array for storing points int dp[element_max + 1] = { 0 }; // Storing frequency of integers for (int i = 0; i < array_size; i++) { mp[A[i]]++; } dp[0] = 0; dp[1] = mp[1]; // Calculation for getting maximum sum // in dp[] array at every steps for (int i = 2; i <= element_max; i++) { dp[i] = max(dp[i - 1], dp[i - 2] + mp[i] * i); } // Returning the maximum sum return dp[element_max];}int main(){ int A[] = { 2, 2, 3, 3, 3, 4 }; // Size of Array int array_size = sizeof(A) / sizeof(A[0]); // Function call cout << MaximumPoints(A, array_size); return 0;} |
Java
// Java program to implement the approachimport java.util.*;import java.util.Arrays;public class GFG { // Function to return Maximum number // of points that can be earned static int MaximumPoints(int A[], int array_size) { // Maximum element in array A int element_max =Arrays.stream(A).max().getAsInt(); HashMap<Integer, Integer> mp = new HashMap<>(); // Dp array for storing points int dp[] = new int[element_max + 1]; // Storing frequency of integers for (int i = 0; i < array_size; i++) { if(mp.containsKey(A[i])){ mp.put(A[i], mp.get(A[i]) + 1); } else{ mp.put(A[i], 1); } } dp[0] = 0; if(mp.containsKey(1)) dp[1] = mp.get(1); // Calculation for getting maximum sum // in dp[] array at every steps for (int i = 2; i <= element_max; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + mp.get(i) * i); } // Returning the maximum sum return dp[element_max]; } // Driver Code public static void main (String[] args) { int A[] = { 2, 2, 3, 3, 3, 4 }; // Size of Array int array_size = A.length; // Function call System.out.print(MaximumPoints(A, array_size)); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python program to implement the approach# Function to return Maximum number# of points that can be earneddef MaximumPoints(A, array_size): # Maximum element in array A element_max = max(A) mp = {} # Dp array for storing points dp = [0 for i in range(element_max + 1)] # Storing frequency of integers for i in range(array_size): if (A[i] in mp): mp[A[i]] = mp[A[i]] + 1 else: mp[A[i]] = 1 if(1 in mp): dp[1] = mp[1] # Calculation for getting maximum sum # in dp[] array at every steps for i in range(2,element_max+1): dp[i] = (max(dp[i - 1], dp[i - 2] + mp[i] * i)) # Returning the maximum sum return dp[element_max]A = [ 2, 2, 3, 3, 3, 4 ]# Size of Arrayarray_size = len(A)# Function callprint(MaximumPoints(A, array_size))# This code is contributed by shinjanpatra |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;using System.Linq;public class GFG { // Function to return Maximum number // of points that can be earned static int MaximumPoints(int[] A, int array_size) { // Maximum element in array A int element_max = A.Max(); Dictionary<int, int> mp = new Dictionary<int, int>(); // Dp array for storing points int[] dp = new int[element_max + 1]; // Storing frequency of integers for (int i = 0; i < array_size; i++) { if (mp.ContainsKey(A[i])) { mp[A[i]] += 1; } else { mp[A[i]] = 1; } } dp[0] = 0; if (mp.ContainsKey(1)) dp[1] = mp[1]; // Calculation for getting maximum sum // in dp[] array at every steps for (int i = 2; i <= element_max; i++) { dp[i] = Math.Max(dp[i - 1], dp[i - 2] + mp[i] * i); } // Returning the maximum sum return dp[element_max]; } // Driver Code public static void Main(string[] args) { int[] A = { 2, 2, 3, 3, 3, 4 }; // Size of Array int array_size = A.Length; // Function call Console.Write(MaximumPoints(A, array_size)); }}// This code is contributed by phasing17. |
Javascript
// JavaScript program to implement the approach// Function to return Maximum number// of points that can be earnedfunction MaximumPoints(A, array_size){ // Maximum element in array A var element_max = Math.max(... A); mp = {}; // Dp array for storing points var dp = []; // Storing frequency of integers for (var i = 0; i < array_size; i++) { if (mp.hasOwnProperty(A[i])) mp[A[i]] = mp[A[i]] + 1; else { mp[A[i]] = 1; } } dp.push(0); if (dp.hasOwnProperty(1)) dp.push(mp[1]); else dp.push(0); // Calculation for getting maximum sum // in dp[] array at every steps for (var i = 2; i <= element_max; i++) { dp.push(Math.max(dp[i - 1], dp[i - 2] + mp[i] * i)); } // Returning the maximum sum return dp[element_max];}var A = [ 2, 2, 3, 3, 3, 4 ];// Size of Arrayvar array_size = A.length;// Function callconsole.log(MaximumPoints(A, array_size));// this code was contributed by phasing17 |
9
Time Complexity: O(N+M)
Auxiliary Space: O(N+M) where M is the maximum element of the array
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
