Given an array arr[] which is of 3*N size, the task is to remove N elements and divide the whole array into two equal parts such that the difference of the sum of the left subarray and right subarray should yield to maximum.
Examples:
Input: arr[] = [5, 4, 4, 2, 3, 3]
Output: 4
Explanation: The ‘2’ elements to be removed are [4, 3].
and when you divide the array into two equal parts after the removal
left subarray= [5, 4], right subarray= [2, 3].
The Sum difference between them is (9-5) = 4Input: arr[] = [4, 5, 6, 1, 2, 8, 7, 9, 3]
Output: 9
Approach:
Split the array into two subarrays at some point i (N <= i <= 2 * N). We remove i – N smallest elements from the first subarray, and (2 * N – i) largest elements from the second subarray. That way, for a given split, we get the largest possible sum_first, and smallest possible sum_second.
Using Max and Min heap to keep track of the smallest and largest elements, respectively. And update the difference.
Follow the below steps to Implement the Idea:
- Initialize a final_diff variable to store the maximum difference between left and right subarray after removal of N elements.
- Run a for loop from N to 2*N and arr[] into two halves left and right.
- Remove i – N smallest elements from left array and 2*N – i largest elements from right array by using Min and Max heap.
- Calculate the sum of N largest values in left array and N smallest values in right array and find out the difference between them and store it in Curr_diff variable.
- Maximize the value of final_diff with curr_diff.
- Return the value of final_diff.
Below is the implementation
C++
#include <iostream>#include <vector>#include <algorithm>#include <queue>#include <unordered_map>#include <climits>using namespace std;// This function returns the (1, n-1) min and max// elements which are to be discarded from the arrayvector<int> best_remove(vector<int> left, vector<int> right, int n) { vector<int> temp; priority_queue<int, vector<int>, greater<int>> leftHeap(left.begin(), left.end()); priority_queue<int, vector<int>, less<int>> rightHeap(right.begin(), right.end()); if (left.size() == n && right.size() > n) { // remove all n elements from the right side int count = 0; while (count < n) { temp.push_back(rightHeap.top()); rightHeap.pop(); count++; } } else if (right.size() == n && left.size() > n) { // remove all element from the left side int count = 0; while (count < n) { temp.push_back(leftHeap.top()); leftHeap.pop(); count++; } } else { int x = left.size() - n; int count = 0; while (count < n - x) { temp.push_back(leftHeap.top()); leftHeap.pop(); count++; } count = 0; while (count < x) { temp.push_back(rightHeap.top()); rightHeap.pop(); count++; } } return temp;}vector<int> remove_elements(vector<int> parent, vector<int> child) { vector<int> result; unordered_map<int, int> childCount; for (int i : child) { int count = childCount[i]; childCount[i] = count + 1; } for (int i : parent) { if (childCount[i] > 0) { childCount[i]--; } else { result.push_back(i); } } return result;}int max_diff(vector<int> arr, int n) { int mid = arr.size() / 2; int left = accumulate(arr.begin(), arr.begin() + mid, 0); int right = accumulate(arr.begin() + mid, arr.end(), 0); return left - right + 1;}int main() { vector<int> arr = {7, 9, 5, 8, 1, 3}; int n = arr.size() / 3; int final_max = INT_MIN; // starting from the index 2 for (int i = n; i <= 2 * n; i++) { vector<int> left(arr.begin(), arr.begin() + i); // dividing the left vector<int> right(arr.begin() + i, arr.end()); // dividing the right sub array vector<int> bestRemoveElements = best_remove(left, right, n); vector<int> dup = arr; vector<int> removeElements = remove_elements(dup, bestRemoveElements); int currMax = max_diff(removeElements, n); final_max = max(final_max, currMax)-1; } cout << "The maximum difference between S1 and S2 is " << final_max << endl; return 0;} |
Java
import java.util.*;import java.util.stream.Collectors;public class Main { // This function returns the (1, n-1) min and max // elements which are to be discarded from the array static List<Integer> best_remove(List<Integer> left, List<Integer> right, int n) { List<Integer> temp = new ArrayList<>(); PriorityQueue<Integer> leftHeap = new PriorityQueue<>(left); PriorityQueue<Integer> rightHeap = new PriorityQueue<>(right); if (left.size() == n && right.size() > n) { // remove all n elements from the right side temp.addAll(rightHeap.stream().sorted(Collections.reverseOrder()).limit(n).collect(Collectors.toList())); } else if (right.size() == n && left.size() > n) { // remove all element from the left side temp.addAll(leftHeap.stream().limit(n).collect(Collectors.toList())); } else { int x = left.size() - n; temp.addAll(leftHeap.stream().limit(n - x).collect(Collectors.toList())); temp.addAll(rightHeap.stream().sorted(Collections.reverseOrder()).limit(x).collect(Collectors.toList())); } return temp; } static List<Integer> remove_elements(List<Integer> parent, List<Integer> child) { List<Integer> result = new ArrayList<>(); Map<Integer, Integer> childCount = new HashMap<>(); for (Integer i : child) { int count = childCount.getOrDefault(i, 0); childCount.put(i, count + 1); } for (Integer i : parent) { if (childCount.containsKey(i) && childCount.get(i) > 0) { childCount.put(i, childCount.get(i) - 1); } else { result.add(i); } } return result; } static int max_diff(List<Integer> arr, int n) { int mid = arr.size() / 2; int left = arr.subList(0, mid).stream().mapToInt(Integer::intValue).sum(); int right = arr.subList(mid, arr.size()).stream().mapToInt(Integer::intValue).sum(); return left - right + 1; } public static void main(String[] args) { List<Integer> arr = Arrays.asList(7, 9, 5, 8, 1, 3); int n = arr.size() / 3; int final_max = Integer.MIN_VALUE; // starting from the index 2 for (int i = n; i <= 2 * n; i++) { List<Integer> left = arr.subList(0, i); // dividing the left List<Integer> right = arr.subList(i, arr.size()); // dividing the right sub array List<Integer> bestRemoveElements = best_remove(left, right, n); List<Integer> dup = new ArrayList<>(arr); List<Integer> removeElements = remove_elements(dup, bestRemoveElements); int currMax = max_diff(removeElements, n); final_max = Math.max(final_max, currMax); } System.out.println("The maximum difference between S1 and S2 is " + final_max); }} |
Python3
import copyimport heapqfrom collections import Counter# This function return the (1, n-1) min and max # elements which are t be discarded from the arraydef best_remove(left, right): temp = [] heapq.heapify(left) heapq.heapify(right) if len(left) == n and len(right) > n: # remove all n elements from the right side temp.extend(heapq.nlargest(n, right)) elif len(right) == n and len(left) > n: # remove all element from the left side temp.extend(heapq.nsmallest(n, left)) else: x = len(left) - n temp.extend(heapq.nsmallest(x, left)+heapq.nlargest(n-x, right)) return tempdef remove_elements(parent, child): f_s = Counter(child) # storing all the elements of right # part to preserve the order incase of duplicates r_h = [] for i in parent: if i in f_s and f_s[i] > 0: f_s[i] -= 1 else: r_h.append(i) # print("after r", left + r_h) return r_h # Remove the child from parent # divide the array # sum the left and right elements # track the curr max sum until the for loops terminates # return the final max difference # print(parent, n, child, m) # print(left, right)def max_diff(arr): # function that calculate the sum of maximum difference between two arrays # print(arr) mid = len(arr)//2 left = sum(arr[:mid]) right = sum(arr[mid:]) return left-rightarr = [7, 9, 5, 8, 1, 3]n = len(arr)//3final_max = -float("inf")# starting from the index 2for i in range(n, 2 * n + 1): left = arr[:i] # dividing the left right = arr[i:] # dividing the right sub array # print(left, right) # functions which returns the best elements to be removed from both sub arrays best_remove_elements = best_remove(left, right) # print(best_remove_elements) dup = [] # copying the original array so that the changes might not reflect dup = copy.deepcopy(arr) # function that returns the array after removing the best_remove elements remove_element = remove_elements(dup, best_remove_elements) # print(remove_element) # return(remove_element) curr_max = max_diff(remove_element) # tracking the maximum final_max = max(final_max, curr_max)print("The maximum difference between S1 and S2 is", final_max) |
C#
using System;using System.Linq;using System.Collections.Generic;public class GFG {// This function return the (1, n-1) min and max // elements which are t be discarded from the arraystatic List<int> BestRemove(List<int> left, List<int> right, int n){ List<int> temp = new List<int>(); left.Sort(); right.Sort(); if (left.Count == n && right.Count > n) // remove all n elements from the right side temp.AddRange(right.OrderByDescending(x => x).Take(n)); else if (right.Count == n && left.Count > n) // remove all element from the left side temp.AddRange(left.OrderBy(x => x).Take(n)); else { int x = left.Count - n; temp.AddRange(left.OrderBy(x => x).Take(x)); temp.AddRange(right.OrderByDescending(x => x).Take(n - x)); } return temp;}static List<int> RemoveElements(List<int> parent, List<int> child){ Dictionary<int, int> f_s = child.GroupBy(x => x).ToDictionary(g => g.Key, g => g.Count()); // storing all the elements of right // part to preserve the order incase of duplicates List<int> r_h = new List<int>(); foreach (int i in parent) { if (f_s.ContainsKey(i) && f_s[i] > 0) f_s[i] -= 1; else r_h.Add(i); } // print("after r", left + r_h) return r_h;}// Remove the child from parent// divide the array// sum the left and right elements// track the curr max sum until the for loops terminates// return the final max difference// print(parent, n, child, m)// print(left, right)// function that calculate the sum of maximum difference between two arrays// print(arr)static int GetMaxDiff(List<int> arr, int n){ int mid = arr.Count / 2; List<int> left = arr.Take(mid).ToList(); List<int> right = arr.Skip(mid).ToList(); int diff = left.Sum() - right.Sum(); return diff;}public static void Main(){ int[] arr = {7, 9, 5, 8, 1, 3}; int n = arr.Length / 3; int finalMax = int.MinValue; // starting from the index 2 for (int i = n; i <= 2 * n; i++) { // functions which returns the best elements to be removed from both sub arrays List<int> bestRemoveElements = BestRemove(arr.Take(i).ToList(), arr.Skip(i).ToList(), n); // copying the original array so that the changes might not reflect List<int> dup = new List<int>(arr); // function that returns the array after removing the best_remove elements List<int> removeElements = RemoveElements(dup, bestRemoveElements); int currMax = GetMaxDiff(removeElements, n); // tracking the maximum finalMax = Math.Max(finalMax, currMax); } Console.WriteLine("The maximum difference between S1 and S2 is {0}", finalMax);}}// This code is contributed by Shivhack999 |
Javascript
function best_remove(left, right, n) { let temp = []; left.sort(); right.sort(); if (left.length == n && right.length > n) { temp.push(...right.sort((a, b) => b - a).slice(0, n)); } else if (right.length == n && left.length > n) { temp.push(...left.sort((a, b) => a - b).slice(0, n)); } else { let x = left.length - n; temp.push(...left.sort((a, b) => a - b).slice(0, x)); temp.push(...right.sort((a, b) => b - a).slice(0, n - x)); } return temp;}function remove_elements(parent, child) { let f_s = child.reduce((acc, val) => { acc[val] = (acc[val] || 0) + 1; return acc; }, {}); let r_h = []; for (let i = 0; i < parent.length; i++) { if (f_s[parent[i]] && f_s[parent[i]] > 0) { f_s[parent[i]]--; } else { r_h.push(parent[i]); } } return r_h;}function max_diff(arr, n) { let mid = Math.floor(arr.length / 2); let left = arr.slice(0, mid); let right = arr.slice(mid); let diff = left.reduce((acc, val) => acc + val, 0) - right.reduce((acc, val) => acc + val, 0); return diff;}let arr = [7, 9, 5, 8, 1, 3];let n = Math.floor(arr.length / 3);let finalMax = Number.MIN_SAFE_INTEGER;for (let i = n; i <= 2 * n; i++) { let bestRemoveElements = best_remove(arr.slice(0, i), arr.slice(i), n); let dup = [...arr]; let removeElement = remove_elements(dup, bestRemoveElements); let currMax = max_diff(removeElement, n); finalMax = Math.max(finalMax, currMax);}console.log("The maximum difference between S1 and S2 is " + finalMax); |
Output
The maximum difference between S1 and S2 is 13
Time Complexity: (N*log(N))
Auxiliary Space: O(N)
Take a part in the ongoing discussion
