Maximize difference between the Sum of the two halves of the Array after removal of N elements

0 0 9 minutes read

Given an integer N and array arr[] consisting of 3 * N integers, the task is to find the maximum difference between first half and second half of the array after the removal of exactly N elements from the array.

Examples:

Input: N = 2, arr[] = {3, 1, 4, 1, 5, 9}
Output: 1
Explanation:
Removal of arr[1] and arr[5] from the array maximizes the difference = (3 + 4) – (1 + 5) = 7 – 6 = 1.

Input: N = 1, arr[] = {1, 2, 3}
Output: -1

Approach:
Follow the steps given below to solve the problem

Traverse the array from the beginning and keep updating the sum of the largest N elements from the beginning of the array.
Similarly, keep updating the sum of the smallest N elements from the end of the array.
Traverse these sums and calculate the differences at each point and update the maximum difference obtained.
Print the maximum difference obtained.

Below is the implementation of the above approach:

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the maximum difference
// possible between the two halves of the array
long long FindMaxDif(vector<long long> a, int m)
{
    int n = m / 3;
 
    vector<long long> l(m + 5), r(m + 5);
 
    // Stores n maximum values from the start
    multiset<long long> s;
 
    for (int i = 1; i <= m; i++) {
 
        // Insert first n elements
        if (i <= n) {
 
            // Update sum of largest n
            // elements from left
            l[i] = a[i - 1] + l[i - 1];
            s.insert(a[i - 1]);
        }
 
        // For the remaining elements
        else {
            l[i] = l[i - 1];
 
            // Obtain minimum value
            // in the set
            long long d = *s.begin();
 
            // Insert only if it is greater
            // than minimum value
            if (a[i - 1] > d) {
 
                // Update sum from left
                l[i] -= d;
                l[i] += a[i - 1];
 
                // Remove the minimum
                s.erase(s.find(d));
 
                // Insert the current element
                s.insert(a[i - 1]);
            }
        }
    }
 
    // Clear the set
    s.clear();
 
    // Store n minimum elements from the end
    for (int i = m; i >= 1; i--) {
 
        // Insert the last n elements
        if (i >= m - n + 1) {
 
            // Update sum of smallest n
            // elements from right
            r[i] = a[i - 1] + r[i + 1];
            s.insert(a[i - 1]);
        }
 
        // For the remaining elements
        else {
 
            r[i] = r[i + 1];
 
            // Obtain the minimum
            long long d = *s.rbegin();
 
            // Insert only if it is smaller
            // than maximum value
            if (a[i - 1] < d) {
 
                // Update sum from right
                r[i] -= d;
                r[i] += a[i - 1];
 
                // Remove the minimum
                s.erase(s.find(d));
 
                // Insert the new element
                s.insert(a[i - 1]);
            }
        }
    }
 
    long long ans = -9e18L;
 
    for (int i = n; i <= m - n; i++) {
 
        // Compare the difference and
        // store the maximum
        ans = max(ans, l[i] - r[i + 1]);
    }
 
    // Return the maximum
    // possible difference
    return ans;
}
 
// Driver Code
int main()
{
 
    vector<long long> vtr = { 3, 1, 4, 1, 5, 9 };
    int n = vtr.size();
 
    cout << FindMaxDif(vtr, n);
 
    return 0;
}

Java

// Java Program to implement
// the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
  // Function to print the maximum difference 
  // possible between the two halves of the array 
  static Long FindMaxDif(List<Long> a, int m) 
  { 
    int n = m / 3; 
 
    Long[] l = new Long[m + 5];
    Long[] r = new Long[m + 5];
 
    for(int i = 0; i < m+5; i++) {
 
      l[i] = r[i] = 0L;
    }
 
    // Stores n maximum values from the start 
    List<Long> s = new ArrayList<Long>(); 
 
    for(int i = 1; i <= m; i++) 
    { 
 
      // Insert first n elements 
      if (i <= n) 
      { 
 
        // Update sum of largest n 
        // elements from left 
        l[i] = a.get(i - 1) + l[i - 1]; 
        s.add(a.get(i - 1)); 
      } 
 
      // For the remaining elements 
      else
      { 
        l[i] = l[i - 1]; 
 
        Collections.sort(s);
 
        // Obtain minimum value 
        // in the set 
        Long d = s.get(0); 
 
        // Insert only if it is greater 
        // than minimum value 
        if (a.get(i - 1) > d) 
        {
 
          // Update sum from left 
          l[i] -= d; 
          l[i] += a.get(i - 1); 
 
          // Remove the minimum 
          s.remove(d); 
 
          // Insert the current element 
          s.add(a.get(i - 1)); 
        } 
      } 
    } 
 
    // Clear the set 
    s.clear(); 
 
    // Store n minimum elements from the end 
    for(int i = m; i >= 1; i--) 
    { 
 
      // Insert the last n elements 
      if (i >= m - n + 1)
      { 
 
        // Update sum of smallest n 
        // elements from right 
        r[i] = a.get(i - 1) + r[i + 1]; 
        s.add(a.get(i - 1)); 
      } 
 
      // For the remaining elements 
      else
      { 
        r[i] = r[i + 1]; 
 
        Collections.sort(s);
 
        // Obtain the minimum 
        Long d = s.get(s.size() - 1); 
 
        // Insert only if it is smaller 
        // than maximum value 
        if (a.get(i - 1) < d)
        { 
 
          // Update sum from right 
          r[i] -= d; 
          r[i] += a.get(i - 1); 
 
          // Remove the minimum 
          s.remove(d); 
 
          // Insert the new element 
          s.add(a.get(i - 1)); 
        } 
      } 
    } 
 
    Long ans = Long.MIN_VALUE; 
 
    for(int i = n; i <= m - n; i++) 
    { 
 
      // Compare the difference and 
      // store the maximum 
      ans = Math.max(ans, l[i] - r[i + 1]); 
    } 
 
    // Return the maximum 
    // possible difference 
    return ans; 
  } 
 
  // Driver Code
  public static void main (String[] args) {
 
    List<Long> vtr = new ArrayList<Long>(
      Arrays.asList(3L, 1L, 4L, 1L, 5L, 9L)); 
    int n = vtr.size(); 
 
    System.out.println(FindMaxDif(vtr, n));
  }
}
 
// This code is contributed by Dharanendra L V.

Python3

# Python3 Program to implement 
# the above approach 
 
# Function to print the maximum difference 
# possible between the two halves of the array 
def FindMaxDif(a, m) : 
 
    n = m // 3
 
    l = [0] * (m + 5)
    r = [0] * (m + 5)
 
    # Stores n maximum values from the start 
    s = [] 
 
    for i in range(1, m + 1) :
 
        # Insert first n elements 
        if (i <= n) :
 
            # Update sum of largest n 
            # elements from left 
            l[i] = a[i - 1] + l[i - 1]
            s.append(a[i - 1])
 
        # For the remaining elements 
        else :
            l[i] = l[i - 1] 
 
            # Obtain minimum value 
            # in the set 
            s.sort()
            d = s[0] 
 
            # Insert only if it is greater 
            # than minimum value 
            if (a[i - 1] > d) :
 
                # Update sum from left 
                l[i] -= d
                l[i] += a[i - 1]
 
                # Remove the minimum 
                s.remove(d)
 
                # Insert the current element 
                s.append(a[i - 1])
 
    # Clear the set 
    s.clear()
 
    # Store n minimum elements from the end 
    for i in range(m, 0, -1) :
 
        # Insert the last n elements 
        if (i >= m - n + 1) : 
 
            # Update sum of smallest n 
            # elements from right 
            r[i] = a[i - 1] + r[i + 1]
            s.append(a[i - 1])
 
        # For the remaining elements 
        else : 
 
            r[i] = r[i + 1]
            s.sort()
             
            # Obtain the minimum 
            d = s[-1]
 
            # Insert only if it is smaller 
            # than maximum value 
            if (a[i - 1] < d) :
 
                # Update sum from right 
                r[i] -= d 
                r[i] += a[i - 1]
 
                # Remove the minimum 
                s.remove(d) 
 
                # Insert the new element 
                s.append(a[i - 1])
 
    ans = -9e18
 
    for i in range(n, m - n + 1) : 
 
        # Compare the difference and 
        # store the maximum 
        ans = max(ans, l[i] - r[i + 1])
 
    # Return the maximum 
    # possible difference 
    return ans
 
# Driver code  
vtr = [ 3, 1, 4, 1, 5, 9 ]
n = len(vtr) 
 
print(FindMaxDif(vtr, n))
 
# This code is contributed by divyesh072019

C#

// C# program to implement 
// the above approach 
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to print the maximum difference 
// possible between the two halves of the array 
static long FindMaxDif(List<long> a, int m) 
{ 
    int n = m / 3; 
     
    long[] l = new long[m + 5];
    long[] r = new long[m + 5];
   
    // Stores n maximum values from the start 
    List<long> s = new List<long>(); 
   
    for(int i = 1; i <= m; i++) 
    { 
         
        // Insert first n elements 
        if (i <= n) 
        { 
             
            // Update sum of largest n 
            // elements from left 
            l[i] = a[i - 1] + l[i - 1]; 
            s.Add(a[i - 1]); 
        } 
         
        // For the remaining elements 
        else
        { 
            l[i] = l[i - 1]; 
             
            s.Sort();
             
            // Obtain minimum value 
            // in the set 
            long d = s[0]; 
   
            // Insert only if it is greater 
            // than minimum value 
            if (a[i - 1] > d) 
            {
                 
                // Update sum from left 
                l[i] -= d; 
                l[i] += a[i - 1]; 
   
                // Remove the minimum 
                s.Remove(d); 
   
                // Insert the current element 
                s.Add(a[i - 1]); 
            } 
        } 
    } 
   
    // Clear the set 
    s.Clear(); 
   
    // Store n minimum elements from the end 
    for(int i = m; i >= 1; i--) 
    { 
         
        // Insert the last n elements 
        if (i >= m - n + 1)
        { 
             
            // Update sum of smallest n 
            // elements from right 
            r[i] = a[i - 1] + r[i + 1]; 
            s.Add(a[i - 1]); 
        } 
   
        // For the remaining elements 
        else
        { 
            r[i] = r[i + 1]; 
             
            s.Sort();
             
            // Obtain the minimum 
            long d = s[s.Count - 1]; 
   
            // Insert only if it is smaller 
            // than maximum value 
            if (a[i - 1] < d)
            { 
                 
                // Update sum from right 
                r[i] -= d; 
                r[i] += a[i - 1]; 
   
                // Remove the minimum 
                s.Remove(d); 
   
                // Insert the new element 
                s.Add(a[i - 1]); 
            } 
        } 
    } 
   
    long ans = (long)(-9e18); 
   
    for(int i = n; i <= m - n; i++) 
    { 
         
        // Compare the difference and 
        // store the maximum 
        ans = Math.Max(ans, l[i] - r[i + 1]); 
    } 
   
    // Return the maximum 
    // possible difference 
    return ans; 
} 
 
// Driver Code
static void Main() 
{
    List<long> vtr = new List<long>(
        new long[]{ 3, 1, 4, 1, 5, 9 }); 
    int n = vtr.Count; 
     
    Console.Write(FindMaxDif(vtr, n));
}
}
 
// This code is contributed by divyeshrabadiya07

Javascript

// JS Program to implement 
// the above approach 
 
// Function to print the maximum difference 
// possible between the two halves of the array 
function FindMaxDif(a, m) 
{
 
    let n = Math.floor(m / 3)
     
    let l = new Array(m + 5).fill(0)
    let r = new Array(m + 5).fill(0)
     
    // Stores n maximum values from the start 
    let s = [] 
     
    let d
 
    for (var i = 1; i < m + 1; i++)
    {
        // Insert first n elements 
        if (i <= n)
        {
            // Update sum of largest n 
            // elements from left 
            l[i] = a[i - 1] + l[i - 1]
            s.push(a[i - 1])
        }
 
        // For the remaining elements 
        else
        {
            l[i] = l[i - 1]
 
             
 
            // Obtain minimum value 
            // in the set 
            s.sort(function(a, b) { return a - b})
            d = s[0] 
 
            // Insert only if it is greater 
            // than minimum value 
            if (a[i - 1] > d)
            {
                // Update sum from left 
                l[i] -= d
                l[i] += a[i - 1]
 
                // Remove the minimum 
                let ind = s.indexOf(d)
                s.splice(ind, 1)
 
                // Insert the current element 
                s.push(a[i - 1])
            }
        }
    }
     
 
    // Clear the set 
    s = []
 
    // Store n minimum elements from the end 
    for (var i = m; i > 0; i--)
    {
 
        // Insert the last n elements 
        if (i >= m - n + 1) 
        {
            // Update sum of smallest n 
            // elements from right 
            r[i] = a[i - 1] + r[i + 1]
            s.push(a[i - 1])
        }
        // For the remaining elements 
        else
        {
            r[i] = r[i + 1]
            s.sort(function(a, b) { return a - b})
             
            // Obtain the minimum 
            d = s[s.length -1]
 
            // Insert only if it is smaller 
            // than maximum value 
            if (a[i - 1] < d)
            {
                // Update sum from right 
                r[i] -= d 
                r[i] += a[i - 1]
 
                // Remove the minimum 
                let ind = s.indexOf(d)
                s.splice(ind, 1)
 
                // Insert the new element 
                s.push(a[i - 1])
            }
        }
    }
     
     
    ans = -100000000
 
    for (var i = n; i < m - n + 1; i++) 
 
        // Compare the difference and 
        // store the maximum 
        ans = Math.max(ans, l[i] - r[i + 1])
 
    // Return the maximum 
    // possible difference 
    return ans
}
 
// Driver code  
let vtr = [ 3, 1, 4, 1, 5, 9 ]
n = vtr.length 
 
console.log(FindMaxDif(vtr, n))
 
// This code is contributed by phasing17

Output:

Time Complexity: O(NlogN)
Auxiliary Space: O(N)

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!