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 arraylong 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 Codeint 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 approachimport 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 Codestatic 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:
1
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!