Maximum Subset Sum possible by negating the entire sum after selecting the first Array element | 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
def maxSubset ( A , flag ) : NEW_LINE INDENT n = len ( A ) NEW_LINE sum = 0 ; NEW_LINE if ( flag ) : NEW_LINE INDENT for i in range ( 1 , n ) : NEW_LINE INDENT A [ i ] = - A [ i ] NEW_LINE DEDENT DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT if ( A [ i ] > 0 ) : NEW_LINE INDENT sum += A [ i ] NEW_LINE DEDENT DEDENT return sum NEW_LINE DEDENT def findBest ( A ) : NEW_LINE INDENT x = maxSubset ( A , 0 ) NEW_LINE y = maxSubset ( A , 1 ) NEW_LINE y = - y NEW_LINE y += A [ 0 ] NEW_LINE y = - y NEW_LINE return max ( x , y ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 1 , 10 , 4 , - 6 , 3 ] NEW_LINE print ( findBest ( A ) ) NEW_LINE DEDENT