text: Maximize sum by choosing elements from different section of a matrix | C ++ program for the above approach ; Function to find the maximum value ; Dp table ; Fill the dp in bottom up manner ; Maximum of the three sections ; Maximum of the first section ; Maximum of the second section ; Maximum of the third section ; If we choose element from section 1 , we cannot have selection from same section in adjacent rows ; Print the maximum sum ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; const int n = 6 , m = 6 ; void maxSum ( long arr [ n ] [ m ] ) { long dp [ n + 1 ] [ 3 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { long m1 = 0 , m2 = 0 , m3 = 0 ; for ( int j = 0 ; j < m ; j ++ ) { if ( ( j / ( m / 3 ) ) == 0 ) { m1 = max ( m1 , arr [ i ] [ j ] ) ; } else if ( ( j / ( m / 3 ) ) == 1 ) { m2 = max ( m2 , arr [ i ] [ j ] ) ; } else if ( ( j / ( m / 3 ) ) == 2 ) { m3 = max ( m3 , arr [ i ] [ j ] ) ; } } dp [ i + 1 ] [ 0 ] = max ( dp [ i ] [ 1 ] , dp [ i ] [ 2 ] ) + m1 ; dp [ i + 1 ] [ 1 ] = max ( dp [ i ] [ 0 ] , dp [ i ] [ 2 ] ) + m2 ; dp [ i + 1 ] [ 2 ] = max ( dp [ i ] [ 1 ] , dp [ i ] [ 0 ] ) + m3 ; } cout << max ( max ( dp [ n ] [ 0 ] , dp [ n ] [ 1 ] ) , dp [ n ] [ 2 ] ) << ' ' ; } int main ( ) { long arr [ n ] [ m ] = { { 1 , 3 , 5 , 2 , 4 , 6 } , { 6 , 4 , 5 , 1 , 3 , 2 } , { 1 , 3 , 5 , 2 , 4 , 6 } , { 6 , 4 , 5 , 1 , 3 , 2 } , { 6 , 4 , 5 , 1 , 3 , 2 } , { 1 , 3 , 5 , 2 , 4 , 6 } } ; maxSum ( arr ) ; return 0 ; }