Maximum Path Sum I | shouldn't the result be that?

What is your hint or solution suggestion?

function maximumPathSumI(triangle) {
  let sum = Math.max(...triangle[0])
  let rout = triangle[0].indexOf(sum)
  for(let i = 1; i < triangle.length; i++){
    let max = Math
.max(triangle[i][rout], triangle[i][rout+1], triangle[i][rout-1]||0)
    if(max === triangle[i][rout+1]) {
      rout++
      console.log(triangle[i][rout])
       sum+=triangle[i][rout]
    }else if(max === triangle[i][rout]){
      console.log(triangle[i][rout])
       sum+=triangle[i][rout]
      }else if(max === triangle[i][rout-1]){
        rout--
        console.log(triangle[i][rout])
       sum+=triangle[i][rout]
      }
  }
  return sum
}

const testTriangle = [[3, 0, 0, 0],
                      [7, 4, 0, 0],
                      [2, 4, 6, 0],
                      [8, 5, 9, 3]];

console.log(maximumPathSumI(numTriangle));

Challenge: Problem 18: Maximum path sum I

Link to the challenge:

Your solution is unfortunately not correct. You do not reach the correct value and pass all tests.

I’m not sure exactly what your code is doing, but you should be able to use a bottom up, dynamic programming approach to reach the solution that only requires n(n+1)/2 additions.

Yeah sure, but can I go downward? it should be okay, because the first test is showing the result of adding the first number to the number on the same column

You can go downward, but the code will be much, much slower. Unfortunately, the combinatorics are working against you and debugging your top down attempt to traverse every single path is hard.

1 Like

Yeah, I’m sure I’m missing something, because when I calculated a combination of adjacent numbers I got an even bigger number than the one the test is telling me I should return. My result of the calculation I did was the same as the result my code is giving, I’ll try to understand the problem more

I’m really not seeing how your code covers all possible paths. You should need a nested loop in there.

It doesn’t, it checks the three numbers under the current one, and adds the biggest to the sum, and then either subtracts from the current index or adds to it, or leaves it as it is.

Ah. A greedy approach can miss the optimal path. The best path for the first 5 rows can then have the worst paths for the next 10 rows, roughly speaking.

Exactly, that’s why I’m so confused, because the sum I got was even bigger, I’m guessing by that I cannot go downwards, should I only check adjacent numbers? I’m so sorry man I know it’s stupid :smile:

Are you just grabbing the biggest value in each row? You don’t get a continuous path that way.

No no, only from the three ones below the current value (The last summed value)

Ok, so that can’t work. You are not checking every single path in your top down approach, so you are omitting the correct path in some cases.

And you seem to be adding something to the sum that you should not be since your result is too large.

Edit: Ah, in the triangle you are not adjacent to the next row at index rout-1, rout, and rout+1…

Thanks man! I’ll try to correct that

So I can’t go downwards, it has to be adjacent?

If you go downwards, you have to check every single path, and those paths have to be steps between legal elements on the next row.

   3
  7 4
 2 4 6
8 5 9 3
[[3, 0, 0, 0]
 [7, 4, 0, 0]
 [2, 4, 6, 0]
 [8, 5, 9, 3]]

For example, from the 4 on the third row, you can only reach the 5 and the 9 on the fourth row.

1 Like

I guess I understood, so I can’t go down-left? Thank you!

In the form that the triangle is stored in, yeah, that’s an invalid direction. The 4 in the third row is not connected to the 8 in the fourth row, for example.

1 Like

Okay, Thank you so much man! I wouldn’t have got that on my own.

1 Like