Maximum possible score that can be obtained by constructing a Binary Tree based on given conditions | Java 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
import java . util . * ; class GFG { static int maxScore ( int [ ] arr ) { int N = arr . length ; N ++ ; int [ ] [ ] dp = new int [ N + 1 ] [ 2 * ( N - 1 ) + 1 ] ; 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 && j <= s ; j ++ ) { dp [ i ] [ s ] = Math . max ( dp [ i ] [ s ] , arr [ j - 1 ] + dp [ i - 1 ] [ s - j ] ) ; } } } return dp [ N ] [ 2 * ( N - 1 ) ] - 1 ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 3 , 0 } ; System . out . print ( maxScore ( arr ) ) ; } }