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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isSubsetSum ( int arr [ ] , int n , int sum ) { bool subset [ 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 ] ; } int findSum ( int * arr , int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += arr [ i ] ; } int val = sqrt ( sum ) ; for ( int i = val ; i >= 0 ; i -- ) { if ( isSubsetSum ( arr , n , i * i ) ) { return i * i ; } } return 0 ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << findSum ( arr , n ) << endl ; return 0 ; }