Maximum subsequence sum from a given array which is a perfect square | Python3 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
import math NEW_LINE def isSubsetSum ( arr , n , sum ) : NEW_LINE INDENT subset = [ [ True for x in range ( sum + 1 ) ] for y in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT subset [ i ] [ 0 ] = True NEW_LINE DEDENT for i in range ( 1 , sum + 1 ) : NEW_LINE INDENT subset [ 0 ] [ i ] = False NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , sum + 1 ) : NEW_LINE INDENT if ( j < arr [ i - 1 ] ) : NEW_LINE INDENT subset [ i ] [ j ] = subset [ i - 1 ] [ j ] NEW_LINE DEDENT if ( j >= arr [ i - 1 ] ) : NEW_LINE INDENT subset [ i ] [ j ] = ( subset [ i - 1 ] [ j ] or subset [ i - 1 ] [ j - arr [ i - 1 ] ] ) NEW_LINE DEDENT DEDENT DEDENT return subset [ n ] [ sum ] NEW_LINE DEDENT def findSum ( arr , n ) : NEW_LINE INDENT sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += arr [ i ] NEW_LINE DEDENT val = int ( math . sqrt ( sum ) ) NEW_LINE for i in range ( val , - 1 , - 1 ) : NEW_LINE INDENT if ( isSubsetSum ( arr , n , i * i ) ) : NEW_LINE INDENT return i * i NEW_LINE DEDENT DEDENT return 0 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE print ( findSum ( arr , n ) ) NEW_LINE DEDENT