Maximum possible score that can be obtained by constructing a Binary Tree based on given conditions | Function to find the maximum score for one possible tree having N nodes N - 1 Edges ; Number of nodes ; Initialize dp [ ] [ ] ; Score with 0 vertices is 0 ; Traverse the nodes from 1 to N ; Find maximum scores for each sum ; Iterate over degree of new node ; Update the current state ; Return maximum score for N node tree having 2 ( N - 1 ) sum of degree ; Driver Code ; Given array of scores ; Function Call
def maxScore ( arr ) : NEW_LINE INDENT N = len ( arr ) NEW_LINE N += 1 NEW_LINE dp = [ [ - 100000 for i in range ( 2 * N ) ] for i in range ( N + 1 ) ] NEW_LINE dp [ 0 ] [ 0 ] = 0 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT for s in range ( 1 , 2 * ( N - 1 ) + 1 ) : NEW_LINE INDENT j = 1 NEW_LINE while j <= N - 1 and j <= s : NEW_LINE INDENT dp [ i ] [ s ] = max ( dp [ i ] [ s ] , arr [ j - 1 ] + dp [ i - 1 ] [ s - j ] ) NEW_LINE j += 1 NEW_LINE DEDENT DEDENT DEDENT return dp [ N ] [ 2 * ( N - 1 ) ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 3 , 0 ] NEW_LINE print ( maxScore ( arr ) ) NEW_LINE DEDENT