Maximum Subset Sum possible by negating the entire sum after selecting the first Array element | C ++ Program to implement the above approach ; Function returns maximum subset sum from the given array = ; Case 2 : Negate values from A [ 1 ] to A [ N - 1 ] ; Include only positives for max subset sum ; Return max sum obtained ; Function to return maximum of the maximum subset sum calculated for the two cases ; Case 1 ; Case 2 ; Modifying the sum ; Including first element ; Negating again ; Return the required answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSubset ( vector < int > & A , bool flag ) { int n = A . size ( ) ; int sum = 0 ; if ( flag ) { for ( int i = 1 ; i < n ; i ++ ) A [ i ] = - A [ i ] ; } for ( int i = 1 ; i < n ; i ++ ) { if ( A [ i ] > 0 ) { sum += A [ i ] ; } } return sum ; } int findBest ( vector < int > A ) { int x = maxSubset ( A , 0 ) ; int y = maxSubset ( A , 1 ) ; y = - y ; y += A [ 0 ] ; y = - y ; return max ( x , y ) ; } int main ( ) { vector < int > A = { 1 , 10 , 4 , -6 , 3 } ; cout << findBest ( A ) << endl ; return 0 ; }