Maximum subsequence sum from a given array which is a perfect square | C # 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
using System ; class GFG { static bool isSubsetSum ( int [ ] arr , int n , int sum ) { bool [ , ] subset = new bool [ n + 1 , sum + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) subset [ i , 0 ] = true ; for ( int i = 1 ; i <= sum ; i ++ ) subset [ 0 , i ] = false ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int 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 ] ; } static int findSum ( int [ ] arr , int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += arr [ i ] ; } int val = ( int ) Math . Sqrt ( sum ) ; for ( int i = val ; i >= 0 ; i -- ) { if ( isSubsetSum ( arr , n , i * i ) ) { return i * i ; } } return 0 ; } public static void Main ( String [ ] args ) { int [ ] arr = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } ; int n = arr . Length ; Console . WriteLine ( findSum ( arr , n ) ) ; } }