Maximize sum by choosing elements from different section of a matrix | Java 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
class GFG { static int n = 6 , m = 6 ; static void maxSum ( long arr [ ] [ ] ) { long [ ] [ ] dp = new long [ n + 1 ] [ 3 ] ; 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 = Math . max ( m1 , arr [ i ] [ j ] ) ; } else if ( ( j / ( m / 3 ) ) == 1 ) { m2 = Math . max ( m2 , arr [ i ] [ j ] ) ; } else if ( ( j / ( m / 3 ) ) == 2 ) { m3 = Math . max ( m3 , arr [ i ] [ j ] ) ; } } dp [ i + 1 ] [ 0 ] = Math . max ( dp [ i ] [ 1 ] , dp [ i ] [ 2 ] ) + m1 ; dp [ i + 1 ] [ 1 ] = Math . max ( dp [ i ] [ 0 ] , dp [ i ] [ 2 ] ) + m2 ; dp [ i + 1 ] [ 2 ] = Math . max ( dp [ i ] [ 1 ] , dp [ i ] [ 0 ] ) + m3 ; } System . out . print ( Math . max ( Math . max ( dp [ n ] [ 0 ] , dp [ n ] [ 1 ] ) , dp [ n ] [ 2 ] ) + "NEW_LINE"); } public static void main ( String [ ] args ) { long arr [ ] [ ] = { { 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 ) ; } }