Find maximum subset sum formed by partitioning any subset of array into 2 partitions with equal sum | Function to find the maximum subset sum ; sum of all elements ; bottom up lookup table ; ; initialising dp table with - 1000000000 where , - 1000000000 means no solution ; Case when diff is 0 ; Putting ith element in g0 ; Putting ith element in g1 ; Ignoring ith element ; Driver code
function maxSum ( a , n ) { var sum = 0 ; for ( var i = 0 ; i < n ; i ++ ) sum += a [ i ] ; var limit = 2 * sum + 1 ; var dp = Array . from ( Array ( n + 1 ) , ( ) => Array ( limit ) ) ; for ( var i = 0 ; i < n + 1 ; i ++ ) { for ( var j = 0 ; j < limit ; j ++ ) dp [ i ] [ j ] = - 1000000000 ; } dp [ 0 ] [ sum ] = 0 ; for ( var i = 1 ; i <= n ; i ++ ) { for ( var j = 0 ; j < limit ; j ++ ) { if ( ( j - a [ i - 1 ] ) >= 0 && dp [ i - 1 ] [ j - a [ i - 1 ] ] != - 1000000000 ) dp [ i ] [ j ] = Math . max ( dp [ i ] [ j ] , dp [ i - 1 ] [ j - a [ i - 1 ] ] + a [ i - 1 ] ) ; if ( ( j + a [ i - 1 ] ) < limit && dp [ i - 1 ] [ j + a [ i - 1 ] ] != - 1000000000 ) dp [ i ] [ j ] = Math . max ( dp [ i ] [ j ] , dp [ i - 1 ] [ j + a [ i - 1 ] ] ) ; if ( dp [ i - 1 ] [ j ] != - 1000000000 ) dp [ i ] [ j ] = Math . max ( dp [ i ] [ j ] , dp [ i - 1 ] [ j ] ) ; } } return dp [ n ] [ sum ] ; } var n = 4 ; var a = [ 1 , 2 , 3 , 6 ] ; document . write ( maxSum ( a , n ) ) ;