JS; maximum path sum exercice in simple arrays; invalid result

Viewed 51

I am doing the euler "maximum path sum" exercice.

 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.

I created a simple method which calculates for each position in the row, the maximum possible value. If we take the previous example, it becomes:

    3
    10 7
    12 14 13
    22 19 23 16
    The maximum value in the last row is 23.

Here is is the code:

function maximumPathSumI(triangle) {
    let columnSum = [];
    for (let row=0; row<triangle.length; row++) {
        let newColumnSum = [];
        for (let column=0; column<triangle[row].length; column++) {
            let maxPreviousValue = getMaxPreviousValueForPosition(column, columnSum);
            newColumnSum[column] = maxPreviousValue + triangle[row][column];
        }
        columnSum = newColumnSum;
    }
    return Math.max(...columnSum);
}

function getMaxPreviousValueForPosition(position, previousValues) {
    let maxValue = previousValues[position] || 0;
    if (position > 0 && maxValue < previousValues[position-1]) maxValue = previousValues[position-1];
    if (position < previousValues.length && maxValue < previousValues[position+1]) maxValue = previousValues[position+1];
    return maxValue;
}

It works with the first test, but doesn't seem to give the right result with this triangel

const testTriangle = [
    [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,],
];

It returns 1116 instead of 1074. When I go through the results row by row, everything seems fine to me.

Here is the intermediary calculations:

[ 75 ]
//[95, 64,],
[ 170, 139 ]
//[17, 47, 82,],
[ 187, 217, 221 ]
//[18, 35, 87, 10,],
[ 235, 256, 308, 231 ]
//[20, 04, 82, 47, 65],
[ 276, 312, 390, 355, 296 ]
//[19, 01, 23, 75, 03, 34,],
[ 331, 391, 413, 465, 358, 330 ]
//[88, 02, 77, 73, 07, 63, 67,],
[ 479, 415, 542, 538, 472, 421, 397 ]
//[99, 65, 04, 28, 06, 16, 70, 92,],
[ 578, 607, 546, 570, 544, 488, 491, 489 ]
//[41, 41, 26, 56, 83, 40, 80, 70, 33,],
[ 648, 648, 633, 626, 653, 584, 571, 561, 522 ]
//[41, 48, 72, 33, 47, 32, 37, 16, 94, 29,],
[ 689, 696, 720, 686, 700, 685, 621, 587, 655, 551 ]
//[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14,],
[ 749, 791, 764, 785, 725, 743, 776, 707, 752, 706, 565 ]
//[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57,],
[ 861, 802, 824, 813, 862, 849, 793, 854, 791, 820, 723, 622 ]
//[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48,],
[ 952, 932, 876, 900, 879, 876, 945, 897, 912, 870, 847, 752, 670 ]
//[63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31,],
[ 1015, 1018, 936, 968, 989, 998, 1012, 975, 985, 928, 939, 934, 792, 701 ]
//[04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23,],
[ 1022, 1080, 1116, 1016, 1021, 1021, 1082, 1110, 1058, 1078, 977, 992, 994, 796, 724 ]
2 Answers

You've misunderstood the challenge. The error in your code is in this line:

maxValue = previousValues[position+1]

Your code allows to look at three different sums from the previous row, but it should only look at two (at the most): the one at position-1 (if valid) and the one at position, but not the one at position+1.

Base on your intermediate calculation, It seem to be correct to find maximum of the last row 1116.

https://codepen.io/tmixab/pen/oNWwYLd

enter image description here

Related