Maximum path sum in an Inverted triangle | SET 2 | Python program 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 left to the number add the maximum of them to it ; Return the maximum sum ; Driver Code
N = 3 NEW_LINE def maxPathSum ( tri ) : NEW_LINE INDENT ans = 0 ; NEW_LINE for i in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( 0 , N - i ) : NEW_LINE INDENT if ( j - 1 >= 0 ) : NEW_LINE INDENT tri [ i ] [ j ] += max ( tri [ i + 1 ] [ j ] , tri [ i + 1 ] [ j - 1 ] ) ; NEW_LINE DEDENT else : NEW_LINE INDENT tri [ i ] [ j ] += tri [ i + 1 ] [ j ] ; NEW_LINE DEDENT ans = max ( ans , tri [ i ] [ j ] ) ; NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT tri = [ [ 1 , 5 , 3 ] , [ 4 , 8 , 0 ] , [ 1 , 0 , 0 ] ] NEW_LINE print ( maxPathSum ( tri ) ) NEW_LINE