text: Maximum possible difference of sum of two subsets of an array | Set 2 | C ++ Program for the above approach ; Stores the positive elements ; Stores the negative elements ; Stores the count of 0 s ; Sum of all positive numbers ; Sum of all negative numbers ; Iterate over the array ; Stores the difference ; Sort the positive numbers in ascending order ; Sort the negative numbers in decreasing order ; Case 1 : Include both positive and negative numbers ; Put all numbers in subset A and one 0 in subset B ; Put all numbers in subset A except the smallest positive number which is put in B ; Put all numbers in subset B and one 0 in subset A ; Place the largest negative number in subset A and remaining in B ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSumAfterPartition ( int arr [ ] , int n ) { vector < int > pos ; vector < int > neg ; int zero = 0 ; int pos_sum = 0 ; int neg_sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] > 0 ) { pos . push_back ( arr [ i ] ) ; pos_sum += arr [ i ] ; } else if ( arr [ i ] < 0 ) { neg . push_back ( arr [ i ] ) ; neg_sum += arr [ i ] ; } else { zero ++ ; } } int ans = 0 ; sort ( pos . begin ( ) , pos . end ( ) ) ; sort ( neg . begin ( ) , neg . end ( ) , greater < int > ( ) ) ; if ( pos . size ( ) > 0 && neg . size ( ) > 0 ) { ans = ( pos_sum - neg_sum ) ; } else if ( pos . size ( ) > 0 ) { if ( zero > 0 ) { ans = ( pos_sum ) ; } else { ans = ( pos_sum - 2 * pos [ 0 ] ) ; } } else { if ( zero > 0 ) { ans = ( -1 * neg_sum ) ; } else { ans = ( neg [ 0 ] - ( neg_sum - neg [ 0 ] ) ) ; } } return ans ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , -5 , -7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maxSumAfterPartition ( arr , n ) ; return 0 ; }