Project Euler : Problem 18 - Maximum path sum I

Problem Statement : Maximum path sum I

Problem 18 : By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is $23$.

$$\color{red}{3}\\ \color{red}{7} \ \ 4\\ 2 \ \ \color{red}{4} \ \ 6\\ 8 \ \ 5 \ \ \color{red}{9} \ \ 3$$

That is, $3 + 7 + 4 + 9 = 23$.

Find the maximum total from top to bottom of the triangle below:

$$75\\ 95 \ \ 64\\ 17 \ \ 47 \ \ 82\\ 18 \ \ 35 \ \ 87 \ \ 10\\ 20 \ \ 04 \ \ 82 \ \ 47 \ \ 65\\ 19 \ \ 01 \ \ 23 \ \ 75 \ \ 03 \ \ 34\\ 88 \ \ 02 \ \ 77 \ \ 73 \ \ 07 \ \ 63 \ \ 67\\ 99 \ \ 65 \ \ 04 \ \ 28 \ \ 06 \ \ 16 \ \ 70 \ \ 92\\ 41 \ \ 41 \ \ 26 \ \ 56 \ \ 83 \ \ 40 \ \ 80 \ \ 70 \ \ 33\\ 41 \ \ 48 \ \ 72 \ \ 33 \ \ 47 \ \ 32 \ \ 37 \ \ 16 \ \ 94 \ \ 29\\ 53 \ \ 71 \ \ 44 \ \ 65 \ \ 25 \ \ 43 \ \ 91 \ \ 52 \ \ 97 \ \ 51 \ \ 14\\ 70 \ \ 11 \ \ 33 \ \ 28 \ \ 77 \ \ 73 \ \ 17 \ \ 78 \ \ 39 \ \ 68 \ \ 17 \ \ 57\\ 91 \ \ 71 \ \ 52 \ \ 38 \ \ 17 \ \ 14 \ \ 91 \ \ 43 \ \ 58 \ \ 50 \ \ 27 \ \ 29 \ \ 48\\ 63 \ \ 66 \ \ 04 \ \ 68 \ \ 89 \ \ 53 \ \ 67 \ \ 30 \ \ 73 \ \ 16 \ \ 69 \ \ 87 \ \ 40 \ \ 31\\ 04 \ \ 62 \ \ 98 \ \ 27 \ \ 23 \ \ 09 \ \ 70 \ \ 98 \ \ 73 \ \ 93 \ \ 38 \ \ 53 \ \ 60 \ \ 04 \ \ 23$$

NOTE: As there are only $16384$ routes, it is possible to solve this problem by trying every route. However, $Problem \ 67$, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! )

Concept and Theory

Lets take the first row and simulate how we get the defined path.

$$3\\ 7 \ \ 4\\ 2 \ \ 4 \ \ 6\\ 8 \ \ 5 \ \ 9 \ \ 3$$

We can use two strategies. Start from the top most element and move downwards or we can start from the bottom row and go upwards.

Lets break it down and see if we can find some sub optimal solution.

Suppose there are only two rows, we can simply add $3$ to both the elements below $3$ and tell which path sum is greater.

$$\color{red}{3}\\ \color{red}{10} \ \ 7$$

Now lets consider another row and see if we can do the same thing as above and find out maximum sum path. But now we have two elements at the top, we can’t simply do as above. Hmmm $\dots$ What about we do same thing and pick which leads to the maximum sum. In the below diagram I have marked all those maximum elements which we can obtain in blue. I have also shown the other sum in green which we will be getting from other element. For eg. $10$ and $4$ will give us $14$ and $7$ and $4$ will give us $11$ for the same position. We will take $14$ as our answer since its the maximum among two possible path sums.

$$\color{red}{3}\\ \color{red}{10} \ \ \ \ \ \ 7 \\ \color{blue}{12} \ \ \color{blue}{(14)} \color{green}{(11)} \ \ \color{blue}{13}$$

So after $3$ rows we have,

$$\color{red}{3}\\ \color{red}{10} \ \ 7 \\ 12 \ \ \color{red}{14} \ \ 13$$

Lets consider last row,

$$\color{red}{3}\\ \color{red}{10} \ \ 7\\ 12 \ \ \color{red}{14} \ \ 13\\ \color{blue}{20} \ \ \color{green}{(17)} \color{blue}{(19)} \ \ \color{blue}{(23)} \color{green}{(22)} \ \ \color{blue}{16}$$ $$\color{red}{3}\\ \color{red}{7} \ \ 4\\ 2 \ \ \color{red}{4} \ \ 6\\ 8 \ \ 5 \ \ \color{red}{9} \ \ 3$$

Voila!!! we found our path with sum $23$. But we have to check all the elements of the last row in the modified grid to find out the maximum or we can keep a variable which will be keeping track of largest sum found so far.

Another approach is to do same but starting from bottom row, and moving up. In this case the first element of first row will be the answer.

Code

/**
 * A function which returns the maximum path sum from top row to bottow row
 *
 * @param grid : the grid
 *
 * @return : maximum path sum
 */
public static int maximumPathSumI(int[][] grid) {

  for (int i = grid.length - 1; i > 0; i--) {
    for (int j = 0; j < grid[i].length - 1; j++) {
      grid[i - 1][j] += (Math.max(grid[i][j], grid[i][j + 1]));
    }
  }

  return grid[0][0];
}

Test Your Skills

Wanna try a harder version of the above problem ? Check this HackerRank problem.

Solution

The solution will remain same as given in the above mentioned post, $maximumPathSumI$, you just need to call it for each test case.

References and Further Readings

• ProjectEuler