Maximize sum of product of neighbouring elements of the element removed from Array | Java program for the above approach ; Stores the dp state where dp [ i ] [ j ] represents the maximum possible score in the subarray from index i to j ; Iterate through all possible lengths of the subarray ; Iterate through all the possible starting indices i having length len ; Stores the rightmost index of the current subarray ; Initial dp [ i ] [ j ] will be 0. ; Iterate through all possible values of k in range [ i + 1 , j - 1 ] ; Return the answer ; Driver Code ; Function Call ; Function Call
import java . io . * ; class GFG { static int maxMergingScore ( int A [ ] , int N ) { int [ ] [ ] dp = new int [ 101 ] [ 101 ] ; for ( int i = 0 ; i < 101 ; i ++ ) { { for ( int j = 0 ; j < 101 ; j ++ ) dp [ i ] [ j ] = 0 ; } } for ( int len = 1 ; len < N ; ++ len ) { for ( int i = 0 ; i + len < N ; ++ i ) { int j = i + len ; dp [ i ] [ j ] = 0 ; for ( int k = i + 1 ; k < j ; ++ k ) { dp [ i ] [ j ] = Math . max ( dp [ i ] [ j ] , dp [ i ] [ k ] + dp [ k ] [ j ] + A [ i ] * A [ j ] ) ; } } } return dp [ 0 ] [ N - 1 ] ; } public static void main ( String [ ] args ) { int N = 4 ; int A [ ] = { 1 , 2 , 3 , 4 } ; System . out . println ( maxMergingScore ( A , N ) ) ; N = 2 ; int B [ ] = { 1 , 55 } ; System . out . println ( maxMergingScore ( B , N ) ) ; } }