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