Reduce Array and Maximize sum by deleting one occurrence of A[i] and all occurrences of A[i]+1 and A[i]-1

0 0 6 minutes read

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) = 6

Input: 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(2^N)
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 earned
int 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 approach
import 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 earned
def 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 Array
array_size = len(A)
 
# Function call
print(MaximumPoints(A, array_size))
 
# This code is contributed by shinjanpatra

C#

// C# code to implement the approach
using 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 earned
function 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 Array
var array_size = A.length;
 
// Function call
console.log(MaximumPoints(A, array_size));
 
// this code was contributed by phasing17

Output

Time Complexity: O(N+M)
Auxiliary Space: O(N+M) where M is the maximum element of the array

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!