Find maximum subset sum formed by partitioning any subset of array into 2 partitions with equal sum | Java implementation for the above mentioned Dynamic Programming approach ; Function to find the maximum subset sum ; sum of all elements ; bottom up lookup table ; ; initialising dp table with INT_MIN where , INT_MIN means no solution ; Case when diff is 0 ; Putting ith element in g0 ; Putting ith element in g1 ; Ignoring ith element ; Driver code
class GFG { final static int INT_MIN = Integer . MIN_VALUE ; static int maxSum ( int a [ ] , int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += a [ i ] ; int limit = 2 * sum + 1 ; int dp [ ] [ ] = new int [ n + 1 ] [ limit ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) { for ( int j = 0 ; j < limit ; j ++ ) dp [ i ] [ j ] = INT_MIN ; } dp [ 0 ] [ sum ] = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 0 ; j < limit ; j ++ ) { if ( ( j - a [ i - 1 ] ) >= 0 && dp [ i - 1 ] [ j - a [ i - 1 ] ] != INT_MIN ) 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 ] ] != INT_MIN ) dp [ i ] [ j ] = Math . max ( dp [ i ] [ j ] , dp [ i - 1 ] [ j + a [ i - 1 ] ] ) ; if ( dp [ i - 1 ] [ j ] != INT_MIN ) dp [ i ] [ j ] = Math . max ( dp [ i ] [ j ] , dp [ i - 1 ] [ j ] ) ; } } return dp [ n ] [ sum ] ; } public static void main ( String [ ] args ) { int n = 4 ; int [ ] a = { 1 , 2 , 3 , 6 } ; System . out . println ( maxSum ( a , n ) ) ; } }