Maximum path sum in a triangle . | Python program for Dynamic Programming implementation of Max sum problem in a triangle ; Function for finding maximum sum ; loop for bottom - up calculation ; for each element , check both elements just below the number and below right to the number add the maximum of them to it ; return the top element which stores the maximum sum ; Driver program to test above function
N = 3 NEW_LINE def maxPathSum ( tri , m , n ) : NEW_LINE INDENT for i in range ( m - 1 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( i + 1 ) : NEW_LINE INDENT if ( tri [ i + 1 ] [ j ] > tri [ i + 1 ] [ j + 1 ] ) : NEW_LINE INDENT tri [ i ] [ j ] += tri [ i + 1 ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT tri [ i ] [ j ] += tri [ i + 1 ] [ j + 1 ] NEW_LINE DEDENT DEDENT DEDENT return tri [ 0 ] [ 0 ] NEW_LINE DEDENT tri = [ [ 1 , 0 , 0 ] , [ 4 , 8 , 0 ] , [ 1 , 5 , 3 ] ] NEW_LINE print ( maxPathSum ( tri , 2 , 2 ) ) NEW_LINE