Related Tags

python
algorithms

# How to find the maximum sum path

Rukhshan Haroon

## Problem

The triangle below is made up of rows of two-digit and one-digit numbers.

Provided that you can only traverse to numbers adjacent to your current position, find the maximum sum of the path that links the two vertical ends of the triangle.

Problem diagram.

For example, if you are on number 12 in the fourth row, you can only traverse to 9 or 2 in the fourth(top to bottom) row, as these are the only two numbers adjacent to your current position.

Hint: An efficient algorithm would incorporate a bottom-top approach.

## Solution

We employ dynamic programming (DP) to solve this puzzle efficiently.

Starting from the second to last row, we can iterate over each element and replace it with either its sum OR the number in the row below on its left or right side, whichever is greater (since we are only allowed to traverse to adjacent nodes). We move from bottom to top and end with the maximum sum in the top-most row of the triangle.

The following illustration shows how this algorithm will work on the example given above:

Visualization of the DP algorithm.

The program below implements this algorithm in Python. The text file contains a triangle of one hundred rows, and the program reads data from it, stores it in a two-dimensional list, and applies dynamic programming to find the path that results in the maximum sum:

main.py
file.txt
def read_data(filename):
table = []
raw = open(filename,'r')
for line in raw:
temp = line.strip().split()
for i in range (len(temp)):
temp[i] = int(temp[i])
table.append(temp)
return table

def calculate_path(table):
for i in range(len(table)-2,-1, -1):
for j in range(0,len(table[i]),1):
table[i][j] += max(table[i+1][j],table[i+1][j+1])
print(table[0][0])

def main():
calculate_path(table)

main()
Solution implemented in Python3.

RELATED TAGS

python
algorithms

CONTRIBUTOR

Rukhshan Haroon