Problem 18: Maximum path sum I

*Difficulty: Easy

Problem:

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.

3
7 4
2 4 6
8 5 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! ;o)

How to solve:

The ‘pyramid’ above can be rewritten as matrix like this

3 0 0 0
7 4 0 0
2 4 6 0
8 5 9 3

We can go bottom up or top down, here I’m using top-down mechanism. By looking ahead one step, you can tell that from the current position, either left or right will produce the maximum path sum. Here’s how it works

Step 1: start from line 1 (because we want to one step ahead, we start at one and look back at line 0)

3 0 0 0

10 7 0 0

Step 2: start from line 2

10 7 0 0

12 14 13 0

(12 = 2 + 10,7, 14 = 4 + max(10,7), 13 = 6 + max(7,0))

Step 3: line 3 (also is the last line – the base of the pyramid)

12 14 13 0

20 19 23 16

(20 = 8+12, 19 = 5 + max(12,14), 23 = 8 + max(13,14), 16 = 3 + max(13,0)

We reach the base of the pyramid, each element in this line contains the maximum sum path from top to itself. The last work we need to do is just find the max value from this line. In this case, is 23. Same for the bigger pyramid below

  75   0   0   0   0   0   0   0   0   0   0   0   0   0   0

  95  64   0   0   0   0   0   0   0   0   0   0   0   0   0

  17  47  82   0   0   0   0   0   0   0   0   0   0   0   0

  18  35  87  10   0   0   0   0   0   0   0   0   0   0   0

  20   4  82  47  65   0   0   0   0   0   0   0   0   0   0

  19   1  23  75   3  34   0   0   0   0   0   0   0   0   0

  88   2  77  73   7  63  67   0   0   0   0   0   0   0   0

  99  65   4  28   6  16  70  92   0   0   0   0   0   0   0

  41  41  26  56  83  40  80  70  33   0   0   0   0   0   0

  41  48  72  33  47  32  37  16  94  29   0   0   0   0   0

  53  71  44  65  25  43  91  52  97  51  14   0   0   0   0

  70  11  33  28  77  73  17  78  39  68  17  57   0   0   0

  91  71  52  38  17  14  91  43  58  50  27  29  48   0   0

  63  66   4  68  89  53  67  30  73  16  69  87  40  31   0

   4  62  98  27  23   9  70  98  73  93  38  53  60   4  23

As in implementation code, you just need to input the pyramid as a string format, then it will split up and calculate the level (the height) of the pyramid.

Solution took 0 ms (the chunk of code that find out the biggest path sum, from the beginning, program run ~30ms )

Implementation: Java

public class Prob18 {

privatestaticint[][] pyramid;

privatestaticString input =

“75 95 64 17 47 82 18 35 87 10 20 4 82 47 65 19 1 23 75 3 34 88”

+ ” 2 77 73 7 63 67 99 65 4 28 6 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 4 68 89 53 67 30 73 16 69 87 40 31 4″

+ ” 62 98 27 23 9 70 98 73 93 38 53 60 4 23″;

//”3 7 4 2 4 6 8 5 9 3″;

publicstaticvoidmain(String[] args) {

//create a pyramid with any given input (string)

long cur = System.currentTimeMillis();

int rowLength = 1;

String[] tokens = input.split(” “);

//calculate the size of the pyramid

int a = 1, b = 1, c = tokens.length*2*-1;

int delta = b*b4*a*c;

int size = (b+(int)Math.sqrt(delta))/2*a;

pyramid = new int[size][size];

//get input

int elementAt = 0;

for(int i = 0; i < pyramid.length; ++i) {

for(int j = 0; j < rowLength; ++j) {

pyramid[i][j] = Integer.valueOf(tokens[elementAt]);

++elementAt;

}

++rowLength;

}

//print out the pyramid

for(int i = 0; i < pyramid.length;++i) {

for(int j = 0; j < pyramid.length; ++j)

System.out.printf(“%4d”, pyramid[i][j]);

System.out.println();

}

int maxPathSum = Integer.MIN_VALUE;

//because we look one step ahead, we

//start from i = 1, and look back i-1

rowLength= 2;

for(int i = 1; i < pyramid.length; ++i) {

for(int j = 0; j < rowLength; ++j)

pyramid[i][j] += (j==0) ? pyramid[i1][j]

: Integer.max(pyramid[i1][j], pyramid[i1][j1]);

//get the max sum path from the base of the pyramid

if(i == pyramid.length1) {

for(int j = 0; j < rowLength; ++j)

maxPathSum= Integer.max(maxPathSum, pyramid[i][j]);

break;

}

++rowLength;

}

System.out.println(maxPathSum);

System.out.println(“Took “ + (System.currentTimeMillis()cur) + ” ms”);

}

}

Advertisements