Flip minimum signs of array elements to get minimum sum of positive elements possible | Function to return the minimum number of elements whose sign must be flipped to get the positive sum of array elements as close to 0 as possible ; boolean variable used for toggling between maps ; Calculate the sum of all elements of the array ; Initializing first map ( dp [ 0 ] ) with INT_MAX because for i = 0 , there are no elements in the array to flip ; Base Case ; For toggling ; Required sum is minimum non - negative So , we iterate from i = 0 to sum and find the first i where dp [ flag ^ 1 ] [ i ] != INT_MAX ; In worst case we will flip max n - 1 elements ; Driver code
def solve ( A , n ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( 2000 ) ] for i in range ( 2000 ) ] NEW_LINE flag = 1 NEW_LINE sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += A [ i ] NEW_LINE DEDENT for i in range ( - sum , sum + 1 ) : NEW_LINE INDENT dp [ 0 ] [ i ] = 10 ** 9 NEW_LINE DEDENT dp [ 0 ] [ 0 ] = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( - sum , sum + 1 ) : NEW_LINE INDENT dp [ flag ] [ j ] = 10 ** 9 NEW_LINE if ( j - A [ i - 1 ] <= sum and j - A [ i - 1 ] >= - sum ) : NEW_LINE INDENT dp [ flag ] [ j ] = dp [ flag ^ 1 ] [ j - A [ i - 1 ] ] NEW_LINE DEDENT if ( j + A [ i - 1 ] <= sum and j + A [ i - 1 ] >= - sum and dp [ flag ^ 1 ] [ j + A [ i - 1 ] ] != 10 ** 9 ) : NEW_LINE INDENT dp [ flag ] [ j ] = min ( dp [ flag ] [ j ] , dp [ flag ^ 1 ] [ j + A [ i - 1 ] ] + 1 ) NEW_LINE DEDENT DEDENT flag = flag ^ 1 NEW_LINE DEDENT for i in range ( sum + 1 ) : NEW_LINE INDENT if ( dp [ flag ^ 1 ] [ i ] != 10 ** 9 ) : NEW_LINE INDENT return dp [ flag ^ 1 ] [ i ] NEW_LINE DEDENT DEDENT return n - 1 NEW_LINE DEDENT arr = [ 10 , 22 , 9 , 33 , 21 , 50 , 41 , 60 ] NEW_LINE n = len ( arr ) NEW_LINE print ( solve ( arr , n ) ) NEW_LINE