Maximize difference between the Sum of the two halves of the Array after removal of N elements | 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
def FindMaxDif ( a , m ) : NEW_LINE INDENT n = m // 3 NEW_LINE l = [ 0 ] * ( m + 5 ) NEW_LINE r = [ 0 ] * ( m + 5 ) NEW_LINE s = [ ] NEW_LINE for i in range ( 1 , m + 1 ) : NEW_LINE INDENT if ( i <= n ) : NEW_LINE INDENT l [ i ] = a [ i - 1 ] + l [ i - 1 ] NEW_LINE s . append ( a [ i - 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT l [ i ] = l [ i - 1 ] NEW_LINE s . sort ( ) NEW_LINE d = s [ 0 ] NEW_LINE if ( a [ i - 1 ] > d ) : NEW_LINE INDENT l [ i ] -= d NEW_LINE l [ i ] += a [ i - 1 ] NEW_LINE s . remove ( d ) NEW_LINE s . append ( a [ i - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT s . clear ( ) NEW_LINE for i in range ( m , 0 , - 1 ) : NEW_LINE INDENT if ( i >= m - n + 1 ) : NEW_LINE INDENT r [ i ] = a [ i - 1 ] + r [ i + 1 ] NEW_LINE s . append ( a [ i - 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT r [ i ] = r [ i + 1 ] NEW_LINE s . sort ( ) NEW_LINE d = s [ - 1 ] NEW_LINE if ( a [ i - 1 ] < d ) : NEW_LINE INDENT r [ i ] -= d NEW_LINE r [ i ] += a [ i - 1 ] NEW_LINE s . remove ( d ) NEW_LINE s . append ( a [ i - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT ans = - 9e18 NEW_LINE for i in range ( n , m - n + 1 ) : NEW_LINE INDENT ans = max ( ans , l [ i ] - r [ i + 1 ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT vtr = [ 3 , 1 , 4 , 1 , 5 , 9 ] NEW_LINE n = len ( vtr ) NEW_LINE print ( FindMaxDif ( vtr , n ) ) NEW_LINE