Maximize the diamonds by choosing different colour diamonds from adjacent boxes | 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 ; Columns are indexed 1 - based
function maxSum ( arr ) { let m = arr . length ; let n = arr [ 0 ] . length - 1 ; let dp = new Array ( m + 1 ) . fill ( 0 ) . map ( ( ) => new Array ( n + 1 ) . fill ( 0 ) ) ; for ( let i = 1 ; i < m ; ++ i ) dp [ i ] [ 1 ] = arr [ i ] [ 1 ] ; for ( let i = 1 ; i < n + 1 ; ++ i ) { for ( let j = 1 ; j < m ; ++ j ) { let mx = 0 ; for ( let k = 1 ; k < m ; ++ k ) { if ( k != j ) { if ( dp [ k ] [ i - 1 ] > mx ) { mx = dp [ k ] [ i - 1 ] ; } } } if ( mx && arr [ j ] [ i ] ) { dp [ j ] [ i ] = arr [ j ] [ i ] + mx ; } } } let ans = - 1 ; for ( let i = 1 ; i <= m ; ++ i ) { if ( dp [ i ] [ n ] ) { ans = Math . max ( ans , dp [ i ] [ n ] ) } ; } return ans ; } let 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 ] , ] ; document . write ( maxSum ( arr ) ) ;