Maximum subsequence sum from a given array which is a perfect square | JavaScript program to implement the above approach ; If sum is 0 , then answer is true ; If sum is not 0 and arr [ ] is empty , then answer is false ; Fill the subset table in bottom up manner ; Function to find the sum ; Find sum of all values ; return the value ; ; Driver Code
function isSubsetSum ( arr , n , sum ) { let subset = new Array ( n + 1 ) ; for ( var i = 0 ; i < subset . length ; i ++ ) { subset [ i ] = new Array ( 2 ) ; } for ( let i = 0 ; i <= n ; i ++ ) subset [ i ] [ 0 ] = true ; for ( let i = 1 ; i <= sum ; i ++ ) subset [ 0 ] [ i ] = false ; for ( let i = 1 ; i <= n ; i ++ ) { for ( let j = 1 ; j <= sum ; j ++ ) { if ( j < arr [ i - 1 ] ) subset [ i ] [ j ] = subset [ i - 1 ] [ j ] ; if ( j >= arr [ i - 1 ] ) subset [ i ] [ j ] = subset [ i - 1 ] [ j ] || subset [ i - 1 ] [ j - arr [ i - 1 ] ] ; } } return subset [ n ] [ sum ] ; } function findSum ( arr , n ) { let sum = 0 ; for ( let i = 0 ; i < n ; i ++ ) { sum += arr [ i ] ; } let val = Math . floor ( Math . sqrt ( sum ) ) ; for ( let i = val ; i >= 0 ; i -- ) { if ( isSubsetSum ( arr , n , i * i ) ) { return i * i ; } } return 0 ; } let arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] ; let n = arr . length ; document . write ( findSum ( arr , n ) ) ;