Maximum sum of a path in a Right Number Triangle | tri [ ] [ ] is a 2D array that stores the triangle , n is number of lines or rows . ; Adding the element of row 1 to both the elements of row 2 to reduce a step from the loop ; Traverse remaining rows ; Loop to traverse columns ; tri [ i ] would store the possible combinations of sum of the paths ; array at n - 1 index ( tri [ i ] ) stores all possible adding combination , finding the maximum one out of them ; driver program
def maxSum ( tri , n ) : NEW_LINE INDENT if n > 1 : NEW_LINE INDENT tri [ 1 ] [ 1 ] = tri [ 1 ] [ 1 ] + tri [ 0 ] [ 0 ] NEW_LINE tri [ 1 ] [ 0 ] = tri [ 1 ] [ 0 ] + tri [ 0 ] [ 0 ] NEW_LINE DEDENT for i in range ( 2 , n ) : NEW_LINE INDENT tri [ i ] [ 0 ] = tri [ i ] [ 0 ] + tri [ i - 1 ] [ 0 ] NEW_LINE tri [ i ] [ i ] = tri [ i ] [ i ] + tri [ i - 1 ] [ i - 1 ] NEW_LINE for j in range ( 1 , i ) : NEW_LINE INDENT if tri [ i ] [ j ] + tri [ i - 1 ] [ j - 1 ] >= tri [ i ] [ j ] + tri [ i - 1 ] [ j ] : NEW_LINE INDENT tri [ i ] [ j ] = tri [ i ] [ j ] + tri [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT tri [ i ] [ j ] = tri [ i ] [ j ] + tri [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT print max ( tri [ n - 1 ] ) NEW_LINE DEDENT tri = [ [ 1 ] , [ 2 , 1 ] , [ 3 , 3 , 2 ] ] NEW_LINE maxSum ( tri , 3 ) NEW_LINE