Maximize the diamonds by choosing different colour diamonds from adjacent boxes | Java implementation of the approach ; Function to return the maximized value ; Number of rows and columns ; Creating the Dp array ; Populating the first column ; Iterating over all the rows ; Getting the ( i - 1 ) th max value ; Adding it to the current cell ; Getting the max sum from the last column ; Driver code ; Columns are indexed 1 - based
import java . io . * ; import java . util . * ; class GFG { static int maxSum ( int [ ] [ ] arr ) { int m = ( int ) arr . length ; int n = ( int ) arr [ 0 ] . length - 1 ; int [ ] [ ] dp = new int [ m + 1 ] [ n + 2 ] ; memset ( arr , 0 , sizeof ( arr ) ) ; for ( int i = 0 ; i <= m ; i ++ ) { for ( int j = 0 ; j <= n + 1 ; j ++ ) { dp [ i ] [ j ] = 0 ; } } for ( int i = 1 ; i < m ; ++ i ) dp [ i ] [ 1 ] = arr [ i ] [ 1 ] ; for ( int i = 1 ; i < n + 1 ; ++ i ) { for ( int j = 1 ; j < m ; ++ j ) { int mx = 0 ; for ( int k = 1 ; k < m ; ++ k ) { if ( k != j ) { if ( dp [ k ] [ i - 1 ] > mx ) { mx = dp [ k ] [ i - 1 ] ; } } } if ( mx != 0 && arr [ j ] [ i ] != 0 ) { dp [ j ] [ i ] = arr [ j ] [ i ] + mx ; } } } int ans = - 1 ; for ( int i = 1 ; i <= m ; ++ i ) { if ( ( dp [ i ] [ n ] ) != 0 ) ans = Math . max ( ans , dp [ i ] [ n ] ) ; } return ans ; } public static void main ( String [ ] args ) { int [ ] [ ] arr = { { 0 , 0 , 0 , 0 , 0 } , { 0 , 10 , 2 , 20 , 0 } , { 0 , 0 , 0 , 5 , 0 } , { 0 , 0 , 0 , 0 , 6 } , { 0 , 4 , 0 , 11 , 5 } , { 0 , 0 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 , 0 } } ; System . out . println ( maxSum ( arr ) ) ; } }