Maximum sum path in a matrix from top to bottom | Python3 implementation to find the maximum sum path in a matrix ; function to find the maximum sum path in a matric ; if there is a single elementif there is a single element only only ; dp [ ] [ ] matrix to store the results of each iteration ; base case , copying elements of last row ; building up the dp [ ] [ ] matrix from bottom to the top row ; finding the maximum diagonal element in the ( i + 1 ) th row if that cell exists ; adding that ' max ' element to the mat [ i ] [ j ] element ; finding the maximum value from the first row of dp [ ] [ ] ; required maximum sum ; Driver program to test above
SIZE = 10 NEW_LINE INT_MIN = - 10000000 NEW_LINE def maxSum ( mat , n ) : NEW_LINE INDENT if n == 1 : NEW_LINE INDENT return mat [ 0 ] [ 0 ] NEW_LINE DEDENT dp = [ [ 0 for i in range ( n ) ] for i in range ( n ) ] NEW_LINE maxSum = INT_MIN NEW_LINE for j in range ( n ) : NEW_LINE INDENT dp [ n - 1 ] [ j ] = mat [ n - 1 ] [ j ] NEW_LINE DEDENT for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT maxi = INT_MIN NEW_LINE if ( ( ( ( j - 1 ) >= 0 ) and ( maxi < dp [ i + 1 ] [ j - 1 ] ) ) ) : NEW_LINE INDENT maxi = dp [ i + 1 ] [ j - 1 ] NEW_LINE DEDENT if ( ( ( ( j + 1 ) < n ) and ( maxi < dp [ i + 1 ] [ j + 1 ] ) ) ) : NEW_LINE INDENT maxi = dp [ i + 1 ] [ j + 1 ] NEW_LINE DEDENT dp [ i ] [ j ] = mat [ i ] [ j ] + maxi NEW_LINE DEDENT DEDENT for j in range ( n ) : NEW_LINE INDENT if ( maxSum < dp [ 0 ] [ j ] ) : NEW_LINE INDENT maxSum = dp [ 0 ] [ j ] NEW_LINE DEDENT DEDENT return maxSum NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 5 , 6 , 1 , 7 ] , [ - 2 , 10 , 8 , - 1 ] , [ 3 , - 7 , - 9 , 11 ] , [ 12 , - 4 , 2 , 6 ] ] NEW_LINE n = 4 NEW_LINE print ( " Maximum ▁ Sum = " , maxSum ( mat , n ) ) NEW_LINE DEDENT