Maximize the diamonds by choosing different colour diamonds from adjacent boxes | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSum ( vector < vector < int > > arr ) { int m = ( int ) arr . size ( ) ; int n = ( int ) arr [ 0 ] . size ( ) - 1 ; int dp [ m ] [ n + 1 ] ; memset ( arr , 0 , sizeof ( arr ) ) ; memset ( dp , 0 , sizeof ( dp ) ) ; 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 and arr [ j ] [ i ] ) { dp [ j ] [ i ] = arr [ j ] [ i ] + mx ; } } } int ans = -1 ; for ( int i = 1 ; i <= m ; ++ i ) { if ( dp [ i ] [ n ] ) ans = max ( ans , dp [ i ] [ n ] ) ; } return ans ; } int main ( ) { vector < vector < 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 } } ; cout << maxSum ( arr ) ; return 0 ; }