Maximize sum by choosing elements from different section of a matrix | Python3 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
import numpy as np NEW_LINE n = 6 ; m = 6 ; NEW_LINE def maxSum ( arr ) : NEW_LINE INDENT dp = np . zeros ( ( n + 1 , 3 ) ) ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT m1 = 0 ; m2 = 0 ; m3 = 0 ; NEW_LINE for j in range ( m ) : NEW_LINE INDENT if ( ( j // ( m // 3 ) ) == 0 ) : NEW_LINE INDENT m1 = max ( m1 , arr [ i ] [ j ] ) ; NEW_LINE DEDENT elif ( ( j // ( m // 3 ) ) == 1 ) : NEW_LINE INDENT m2 = max ( m2 , arr [ i ] [ j ] ) ; NEW_LINE DEDENT elif ( ( j // ( m // 3 ) ) == 2 ) : NEW_LINE INDENT m3 = max ( m3 , arr [ i ] [ j ] ) ; NEW_LINE DEDENT DEDENT dp [ i + 1 ] [ 0 ] = max ( dp [ i ] [ 1 ] , dp [ i ] [ 2 ] ) + m1 ; NEW_LINE dp [ i + 1 ] [ 1 ] = max ( dp [ i ] [ 0 ] , dp [ i ] [ 2 ] ) + m2 ; NEW_LINE dp [ i + 1 ] [ 2 ] = max ( dp [ i ] [ 1 ] , dp [ i ] [ 0 ] ) + m3 ; NEW_LINE DEDENT print ( max ( max ( dp [ n ] [ 0 ] , dp [ n ] [ 1 ] ) , dp [ n ] [ 2 ] ) ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT 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 ] ] ; NEW_LINE maxSum ( arr ) ; NEW_LINE DEDENT