Given an array A[] of N numbers, we need to maximize the sum of selected numbers following the given operation:
- At each step, you need to select a number Ai, delete one occurrence and add it to the sum.
- Delete one occurrence of Ai-1 and Ai+1 (if they exist in the array).
- Repeat these steps until the array gets empty.
Examples:
Input: A[] = {1, 2, 3}
Output: 4
Explanation: At first step we select 1, so 1 and 2 are deleted from the sequence leaving us with 3.
Then we select 3 from the sequence and delete it.
So the sum of selected numbers is 1+3 = 4.Input: A[] = {1, 2, 2, 2, 3, 4}
Output: 10
Explanation: Select one of the 2’s from the array.
So 2, 2-1, 2+1 will be deleted.
Now array is {2, 2, 4}, since 1 and 3 are deleted.
Select 2 in next two steps, and then select 4 in the last step.
We get a sum of 2 + 2 + 2 + 4 = 10 which is the maximum possible.
Approach: The idea to solve the problem is:
Pre-calculate the occurrence of all numbers ( say x ) in the array A[] and then iterate from maximum number to minimum number.
For each number x delete one occurrence of x and x-1(if exists) and add x to the sum until x is completely removed.
Follow the steps mentioned below to solve the problem
- Calculate the MAX value in the array.
- Create an array of size MAX and store the occurrences of each element in it.
- Since we want to maximize our answer, we will start iterating from the MAX value to 0.
- If the occurrence of the ith element is greater than 0, then add it to our answer decrease the occurrences of the i-1th element by 1, and also decrease the occurrence of ith by 1 since we have added it to our answer.
- We don’t have to decrease the occurrence of the i+1th element because we are already starting from the end so i+1th is already processed.
- There might be multiple occurrences of the ith element that’s why do not decrease i yet, to stay on the same element.
Below is the implementation of the above idea:
C++
// CPP program to Maximize the sum of selected// numbers by deleting three consecutive numbers.#include <bits/stdc++.h>using namespace std;// function to maximize the sum of selected numbersint maximizeSum(int arr[], int n){ // Largest element in the array int mx = -1; for (int i = 0; i < n; i++) { mx = max(mx, arr[i]); } // An array to count the occurrence of each element int freq[mx + 1]; memset(freq, 0, sizeof(freq)); for (int i = 0; i < n; i++) { freq[arr[i]]++; } // ans to store the result int ans = 0, i = mx; // Using the above mentioned approach while (i > 0) { // if occurrence is greater than 0 if (freq[i] > 0) { // add it to ans ans += i; // decrease i-1th element by 1 freq[i - 1]--; // decrease ith element by 1 freq[i]--; } else { // decrease i i--; } } return ans;}// Driver codeint main(){ int a[] = { 1, 2, 3 }; int n = sizeof(a) / sizeof(a[0]); cout << maximizeSum(a, n); return 0;} |
Java
// Java implementation of the approachimport java.math.*;import java.util.*;class GFG { // Function to maximise the sum of selected numbers // by deleting occurrences of Ai-1 and Ai+1 public static int getMaximumSum(int arr[]) { // Number of elements in the array int n = arr.length; // Largest element in the array int max = -1; for (int i = 0; i < n; i++) { max = Math.max(max, arr[i]); } // An array to count the occurrence of each element int[] freq = new int[max + 1]; for (int i = 0; i < n; i++) { freq[arr[i]]++; } // ans to store the result int ans = 0, i = max; // Using the above mentioned approach while (i > 0) { // if occurrence is greater than 0 if (freq[i] > 0) { // add it to ans ans += i; // decrease i-1th element by 1 freq[i - 1]--; // decrease ith element by 1 freq[i]--; } else { // decrease i i--; } } return ans; } // Driver code public static void main(String[] args) { int[] a = { 1, 2, 3 }; System.out.println(getMaximumSum(a)); }} |
Python3
# Python3 program to Maximize the sum of selected# numbers by deleting three consecutive numbers.# function to maximize the sum of# selected numbersdef maximizeSum(a, n): # maximum in the sequence maximum = max(a) # stores the occurrences of the numbers ans = dict.fromkeys(range(0, n + 1), 0) # marks the occurrence of every # number in the sequence for i in range(n): ans[a[i]] += 1 # ans to store the result result = 0 i = maximum # Using the above mentioned approach while i > 0: # if occurrence is greater than 0 if ans[i] > 0: # add it to ans result += i # decrease i-1th element by 1 ans[i-1] -= 1 # decrease ith element by 1 ans[i] -= 1 else: # decrease i i -= 1 return result# Driver codeif __name__ == "__main__": a = [1, 2, 3] n = len(a) print(maximizeSum(a, n))# This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;using System.Linq;class GFG { // Function to maximise the sum of selected numbers // by deleting occurrences of Ai-1 and Ai+1 static int getMaximumSum(int[] arr) { // Number of elements in the array int n = arr.Length; // Largest element in the array int max = arr.Max(); // An array to count the occurrence of each element int[] freq = new int[max + 1]; for (int j = 0; j < n; j++) { freq[arr[j]]++; } // ans to store the result int ans = 0, i = max; // Using the above mentioned approach while (i > 0) { // if occurrence is greater than 0 if (freq[i] > 0) { // add it to ans ans += i; // decrease i-1th element by 1 freq[i - 1]--; // decrease ith element by 1 freq[i]--; } else { // decrease i i--; } } return ans; } // Driver code public static void Main(string[] args) { int[] a = { 1, 2, 3 }; Console.Write(getMaximumSum(a)); }}// This code is contributed by rock_cool |
Javascript
<script> // Javascript implementation of the approach // Function to maximise the sum of selected numbers //by deleting occurrences of Ai-1 and Ai+1 function getMaximumSum(arr) { // Number of elements in the array let n = arr.length; // Largest element in the array let max = Number.MIN_VALUE; for(let i = 0; i < n; i++) { max = Math.max(max, arr[i]); } // An array to count the occurrence of each element let freq = new Array(max + 1); freq.fill(0); for(let j = 0; j < n; j++) { freq[arr[j]]++; } // ans to store the result let ans = 0, i=max; // Using the above mentioned approach while(i>0){ // if occurrence is greater than 0 if(freq[i] > 0){ // add it to ans ans += i; // decrease i-1th element by 1 freq[i-1]--; // decrease ith element by 1 freq[i]--; }else{ // decrease i i--; } } return ans; } let a = [1, 2, 3]; document.write(getMaximumSum(a)); // This code is contributed by suresh07.</script> |
Output
4
Time Complexity: (Amax + Highest occurrence of element in arr), because if the frequency is greater than 1 then we are processing that element multiple times.
Auxiliary Space: O(Amax ), where Amax is the maximum element present in array A[].
Second Approach: Using Hash Map/Unordered Map concept.
Intuition:
As we know we have given sorted array, so we store all the elements occurrence in hash map and we again we traverse the array and check element is present or not in the hash map if present we add it in our answer and remove its occurrence.
Follow the steps mentioned below to solve the problem
- First create hash map or unordered map
- Then add all element of array in map
- Again traverse the array from back because you have given sorted array and start checking element is present or not in the map if present add to the answer and decrease the frequency of element in the map and also check the condition one less than element ( Ai-1 (if exists)) is present or not if present decrease the frequency of element in the map.
Below is the implementation of the above idea:
C++
#include <bits/stdc++.h>using namespace std;int maximizeSum(int arr[], int n){ int Total_sum = 0; // Creating hash map unordered_map<int, int> ha; // Adding all element in hash map for (int i = n - 1; i >= 0; i--) { ha[arr[i]]++; } // Again traversing and checking element is present // or not in hash map for (int i = n - 1; i >= 0; i--) { if (ha.count(arr[i])) { // Adding in total sum Total_sum += arr[i]; ha[arr[i]]--; // if element frequency in map become zero // than remove that element if (ha[arr[i]] == 0) ha.erase(arr[i]); if (ha.count(arr[i] - 1)) { ha[arr[i] - 1]--; // if element frequency in map become // zero than remove that element if (ha[arr[i] - 1] == 0) ha.erase(arr[i] - 1); } } } return Total_sum;}int main(){ int arr[] = { 1, 2, 2, 2, 3, 4 }; int n = 6; cout << maximizeSum(arr, n) << endl;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.HashMap;class GFG { // Driver code public static void main(String[] args) { int[] arr = { 1, 2, 2, 2, 3, 4 }; int n = 6; System.out.println(maximizeSum(arr, n)); } public static int maximizeSum(int arr[], int n) { int Total_sum = 0; // Creating hash map HashMap<Integer, Integer> ha = new HashMap<>(); // Adding all element in hash map for (int i = n - 1; i >= 0; i--) { ha.put(arr[i], ha.getOrDefault(arr[i], 0) + 1); } // Again traversing and checking element is present // or not in hash map for (int i = n - 1; i >= 0; i--) { if (ha.containsKey(arr[i])) { // Adding in total sum Total_sum += arr[i]; ha.put(arr[i], ha.getOrDefault(arr[i], 0) - 1); // if element frequency in map become zero // than remove that element if (ha.get(arr[i]) == 0) ha.remove(arr[i]); if (ha.containsKey(arr[i] - 1)) { ha.put(arr[i] - 1, ha.getOrDefault(arr[i] - 1, 0) - 1); // if element frequency in map become // zero than remove that element if (ha.get(arr[i] - 1) == 0) ha.remove(arr[i] - 1); } } } return Total_sum; }} |
Python3
from collections import defaultdictdef maximizeSum(arr, n): total_sum = 0 ha = defaultdict(int) # Adding all element in hash map for i in range(n - 1, -1, -1): ha[arr[i]] += 1 # Again traversing and checking element is present # or not in hash map for i in range(n - 1, -1, -1): if arr[i] in ha: # Adding in total sum total_sum += arr[i] ha[arr[i]] -= 1 # if element frequency in map become zero # than remove that element if ha[arr[i]] == 0: ha.pop(arr[i]) if arr[i] - 1 in ha: ha[arr[i] - 1] -= 1 # if element frequency in map become # zero than remove that element if ha[arr[i] - 1] == 0: ha.pop(arr[i] - 1) return total_sumarr = [1, 2, 2, 2, 3, 4]n = 6print(maximizeSum(arr, n))# This code is contributed by shvrekhan. |
C#
// C# implementation of above approachusing System;using System.Collections;using System.Collections.Generic;class GFG { // Driver code public static void Main(string[] args) { int[] arr = { 1, 2, 2, 2, 3, 4 }; int n = 6; Console.WriteLine(maximizeSum(arr, n)); } public static int maximizeSum(int[] arr, int n) { int Total_sum = 0; // Creating hash map Dictionary<int, int> ha = new Dictionary<int, int>(); // Adding all element in hash map for (int i = n - 1; i >= 0; i--) { if (ha.ContainsKey(arr[i])) { int x = ha[arr[i]]; ha.Remove(arr[i]); ha.Add(arr[i], x + 1); } else { ha.Add(arr[i], 1); } } // Again traversing and checking element is present // or not in hash map for (int i = n - 1; i >= 0; i--) { if (ha.ContainsKey(arr[i])) { // Adding in total sum Total_sum += arr[i]; int x = ha[arr[i]]; ha.Remove(arr[i]); ha.Add(arr[i], x - 1); // if element frequency in map become zero // than remove that element if (ha[arr[i]] == 0) ha.Remove(arr[i]); if (ha.ContainsKey(arr[i] - 1)) { int y = ha[arr[i] - 1]; ha.Remove(arr[i] - 1); ha.Add(arr[i] - 1, y - 1); // if element frequency in map become // zero than remove that element if (ha[arr[i] - 1] == 0) ha.Remove(arr[i] - 1); } } } return Total_sum; }}// This code is contributed by karandeep1234 |
Javascript
function maximizeSum(arr, n) { let totalSum = 0; // Creating hash map const ha = new Map(); // Adding all element in hash map for (let i = n - 1; i >= 0; i--) { if (ha.has(arr[i])) { ha.set(arr[i], ha.get(arr[i]) + 1); } else { ha.set(arr[i], 1); } } // Again traversing and checking element is present // or not in hash map for (let i = n - 1; i >= 0; i--) { if (ha.has(arr[i])) { // Adding in total sum totalSum += arr[i]; ha.set(arr[i], ha.get(arr[i]) - 1); // if element frequency in map become zero // than remove that element if (ha.get(arr[i]) === 0) { ha.delete(arr[i]); } if (ha.has(arr[i] - 1)) { ha.set(arr[i] - 1, ha.get(arr[i] - 1) - 1); // if element frequency in map become // zero than remove that element if (ha.get(arr[i] - 1) === 0) { ha.delete(arr[i] - 1); } } } } return totalSum;}const arr = [1, 2, 2, 2, 3, 4];const n = 6;console.log(maximizeSum(arr, n)); |
Output
10
Time Complexity: O(n) because we traverse two times in the array ( n + n = 2n) but as we ignore constant it becomes O(n).
Auxiliary Space: O(n) because we are using a map.
Efficient Approach: As the given array is sorted, start iterating from the end and find if the current number – 1 exists in the array, then mark that number as -1. Mark the current number as -1, and add the current element to the answer. After the traversal, add all positive elements to the answer.
Illustration
array – > 1 , 2, 2, 2, 3, 4
sum – > 0start the traversal from the end , make two variables i and index, i is for traversal and index for checking if there exists a number which is equal to array[i]-1
i = 5 , index = 5 – now decrement index while index >= 0 and array[index] == array[i] , now i = 5 , and index = 4 , add array[i] to sum and change the values at i and index to -1, decrement index.
array -> 1, 2, 2, 2, -1, -1
sum -> 4——————————————————
decrement i , if array[i] == -1 , do nothing
———————————————————
now i = 3 and index = 3
after decrementing index – i = 3 , index = 0
array -> -1, 2, 2, -1, -1, -1
sum -> 6
decrement index.———————————————————
i = 2 , index = -1
now as index = -1 , we add the number currently at i and then exit the loop
array -> -1, 2, -1, -1, -1, -1
sum -> 8
now exit out of the loop——————————————————
now we iterate through the array once and add every number (which is not -1) to the variable sum
sum – > 10
final answer is 10
Below is the implementation of the above approach:
C++
// C++ code for given approach#include <bits/stdc++.h>using namespace std;// Function for finding maximum and value pairint maximizeSum(int arr[], int n) { int sum = 0; int i; int index = n - 1; for (i = n - 1; i >= 0; i--) { if (arr[i] == -1) { continue; } // to find the first occurrence of a number // lesser than at i while (index >= 0 && arr[i] == arr[index]) { index--; } // to take care of out of bounds exception if (index == -1) { sum += arr[i]; i--; break; } if (arr[i] - 1 == arr[index]) { sum += arr[i]; // all used numbers are marked as -1 arr[i] = -1; arr[index] = -1; index--; continue; } else { sum += arr[i]; arr[i] = -1; } } // to add the remaining numbers while (i >= 0) { if (arr[i] != -1) { sum += arr[i]; } i--; } return sum;}// Driver program to run the caseint main() { int arr[] = { 1, 2, 2, 2, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int sum = maximizeSum(arr, n); cout << sum;}// This code is contributed by Ajaymakvana. |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { // Function for finding maximum and value pair public static int maximizeSum(int arr[], int n) { int sum = 0; int i; int index = arr.length - 1; for (i = arr.length - 1; i >= 0; i--) { if (arr[i] == -1) { continue; } // to find the first occurrence of a number // lesser than at i while (index >= 0 && arr[i] == arr[index]) { index--; } // to take care of out of bounds exception if (index == -1) { sum += arr[i]; i--; break; } if (arr[i] - 1 == arr[index]) { sum += arr[i]; // all used numbers are marked as -1 arr[i] = -1; arr[index] = -1; index--; continue; } else { sum += arr[i]; arr[i] = -1; } } // to add the remaining numbers while (i >= 0) { if (arr[i] != -1) { sum += arr[i]; } i--; } return sum; } public static void main(String[] args) { int sum = maximizeSum( new int[] { 1, 2, 2, 2, 3, 4 }, 6); System.out.println(sum); }} |
Python3
# Function for finding maximum and value pairdef maximizeSum(arr,n): sum = 0 index = len(arr) - 1 for i in range(len(arr) - 1,-1,-1): if (arr[i] == -1): continue # to find the first occurrence of a number # lesser than at i while (index >= 0 and arr[i] == arr[index]): index = index - 1 # to take care of out of bounds exception if (index == -1): sum = sum + arr[i] i = i - 1 break if (arr[i] - 1 == arr[index]): sum = sum + arr[i] # all used numbers are marked as -1 arr[i] = -1 arr[index] = -1 index = index - 1 continue else: sum = sum + arr[i] arr[i] = -1 # to add the remaining numbers while (i >= 0): if (arr[i] != -1): sum = sum + arr[i] i = i - 1 return sumsum = maximizeSum([ 1, 2, 2, 2, 3, 4 ], 6)print(sum)# This code is contributed by manikishorgzva |
C#
// C# code for given approachusing System;public class GFG { // Function for finding maximum and value pair public static int maximizeSum(int[] arr, int n) { int sum = 0; int i; int index = arr.Length - 1; for (i = arr.Length - 1; i >= 0; i--) { if (arr[i] == -1) { continue; } // to find the first occurrence of a number // lesser than at i while (index >= 0 && arr[i] == arr[index]) { index--; } // to take care of out of bounds exception if (index == -1) { sum += arr[i]; i--; break; } if (arr[i] - 1 == arr[index]) { sum += arr[i]; // all used numbers are marked as -1 arr[i] = -1; arr[index] = -1; index--; continue; } else { sum += arr[i]; arr[i] = -1; } } // to add the remaining numbers while (i >= 0) { if (arr[i] != -1) { sum += arr[i]; } i--; } return sum; } public static void Main(string[] args) { int sum = maximizeSum( new int[] { 1, 2, 2, 2, 3, 4 }, 6); Console.WriteLine(sum); }}// This code is contributed by karandeep1234. |
Javascript
function maximizeSum(arr) { // Initialize sum and index variables let sum = 0; let i; let index = arr.length - 1; // Iterate through the array in reverse for (i = arr.length - 1; i >= 0; i--) { // Skip iteration if the current element is -1 if (arr[i] === -1) { continue; } // Find the first occurrence of a number lesser than the current element while (index >= 0 && arr[i] === arr[index]) { index--; } // If no such number is found, add the current element to the sum and break if (index === -1) { sum += arr[i]; i--; break; } // If a number one less than the current element is found, add the current element to the sum and mark both elements as used (-1) if (arr[i] - 1 === arr[index]) { sum += arr[i]; arr[i] = -1; arr[index] = -1; index--; continue; } // Otherwise, add the current element to the sum and mark it as used (-1) else { sum += arr[i]; arr[i] = -1; } } // Add any remaining unused elements to the sum while (i >= 0) { if (arr[i] !== -1) { sum += arr[i]; } i--; } return sum;}console.log(maximizeSum([1, 2, 2, 2, 3, 4])); |
Output
10
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
