Hackerrank - Project Euler+ #018 - Maximum path sum I

Hackerrank - Problem description

The problem description - Hackerrank.

Solution

I read and store all number into lists by rows.
I start from the bottom and take last 2 lines. I sum a number from upper row with numbers from lower row on the left and right side. I do it for every number in the upper row. Then I find the greatest sum - with left or with right. I use this greatest sum and switch all numbers in the upper row with it for every item. I delete bottom line and continue the process until I reach only top of the triangle.

Given example:

Last 2 rows:
Start with 2:

10 is greater than 7 and 2 is replaced with 10.
4:

It is replaced with 13
6:

Replaced with 9

There is a following state after first iteration:

Second iteration:

I the end:

I created solution in:

All solutions are also available on my GitHub profile.

Java

Leave a Reply