Maximum possible score that can be obtained by constructing a Binary Tree based on given conditions | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxScore ( vector < int > & arr ) { int N = arr . size ( ) ; N ++ ; vector < vector < int > > dp ( N + 1 , vector < int > ( 2 * N , -100000 ) ) ; dp [ 0 ] [ 0 ] = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { for ( int s = 1 ; s <= 2 * ( N - 1 ) ; s ++ ) { for ( int j = 1 ; j <= N - 1 and j <= s ; j ++ ) { dp [ i ] [ s ] = max ( dp [ i ] [ s ] , arr [ j - 1 ] + dp [ i - 1 ] [ s - j ] ) ; } } } return dp [ N ] [ 2 * ( N - 1 ) ] ; } int main ( ) { vector < int > arr = { 1 , 3 , 0 } ; cout << maxScore ( arr ) ; return 0 ; }