Flip minimum signs of array elements to get minimum sum of positive elements possible | C # implementation of the above approach : ; 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
using System ; class GFG { public static int solve ( int [ ] A , int n ) { int [ , ] dp = new int [ 2000 , 2000 ] ; int flag = 1 ; int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += A [ i ] ; for ( int i = - sum ; i <= sum ; i ++ ) { try { dp [ 0 , i ] = int . MaxValue ; } catch ( Exception e ) { } } dp [ 0 , 0 ] = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= sum ; j ++ ) { try { dp [ flag , j ] = int . MaxValue ; if ( j - A [ i - 1 ] <= sum && j - A [ i - 1 ] >= - sum ) dp [ flag , j ] = dp [ flag ^ 1 , j - A [ i - 1 ] ] ; if ( j + A [ i - 1 ] <= sum && j + A [ i - 1 ] >= - sum && dp [ flag ^ 1 , j + A [ i - 1 ] ] != int . MaxValue ) dp [ flag , j ] = Math . Min ( dp [ flag , j ] , dp [ flag ^ 1 , j + A [ i - 1 ] ] + 1 ) ; } catch ( Exception e ) { } } flag = flag ^ 1 ; } for ( int i = 0 ; i <= sum ; i ++ ) { if ( dp [ flag ^ 1 , i ] != int . MaxValue ) return dp [ flag ^ 1 , i ] ; } return n - 1 ; } public static void Main ( String [ ] args ) { int [ ] arr = { 10 , 22 , 9 , 33 , 21 , 50 , 41 , 60 } ; int n = arr . Length ; Console . WriteLine ( solve ( arr , n ) ) ; } }