Maximum sum of a path in a Right Number Triangle - GeeksforGeeks
Given a right triangle of numbers, find the largest of the sum of numbers that appear on the paths starting from the top towards the base, so that on each path the next number is located directly below or below-and-one-place-to-the-right.
Read full article from Maximum sum of a path in a Right Number Triangle - GeeksforGeeks
Given a right triangle of numbers, find the largest of the sum of numbers that appear on the paths starting from the top towards the base, so that on each path the next number is located directly below or below-and-one-place-to-the-right.
The idea is to find largest sum ending at every cell of last row and return maximum of these sums. We can recursively compute these sums by recursively considering above two cells. Since there are overlapping subproblems, we use dynamic programming to find the maximum sum ending at particular cell of last row.
# tri[][] is a 2D array that stores the
# triangle, n is number of lines or rows.
def
maxSum(tri, n):
# Adding the element of row 1 to both the
# elements of row 2 to reduce a step from
# the loop
if
n >
1
:
tri[
1
][
1
]
=
tri[
1
][
1
]
+
tri[
0
][
0
]
tri[
1
][
0
]
=
tri[
1
][
0
]
+
tri[
0
][
0
]
# Traverse remaining rows
for
i
in
range
(
2
, n):
tri[i][
0
]
=
tri[i][
0
]
+
tri[i
-
1
][
0
]
tri[i][i]
=
tri[i][i]
+
tri[i
-
1
][i
-
1
]
# Loop to traverse columns
for
j
in
range
(
1
, i):
# Checking the two conditions, directly below
# and below right. Considering the greater one
# tri[i] would store the possible combinations
# of sum of the paths
if
tri[i][j]
+
tri[i
-
1
][j
-
1
] >
=
tri[i][j]
+
tri[i
-
1
][j]:
tri[i][j]
=
tri[i][j]
+
tri[i
-
1
][j
-
1
]
else
:
tri[i][j]
=
tri[i][j]
+
tri[i
-
1
][j]
# array at n-1 index (tri[i]) stores all possible
# adding combination, finding the maximum one
# out of them
print
max
(tri[n
-
1
])