JS；在简单数组中找到最大路径和练习；无效结果。

Question

我正在做欧拉计划中的“最大路径和”练习。

 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.

我创建了一个简单的方法，计算每个位置在行中的最大可能值。如果我们采取先前的例子，它将变为：

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

以下是代码：

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;
}

第一个测试是有效的，但在这个三角形中似乎没有得出正确的结果

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,],
];

它返回1116而不是1074。 逐行检查结果时，对我来说一切似乎都很好。

以下是中间计算：

[ 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 ]

- baloo

Answer 1

你误解了这个挑战。你代码中的错误在这一行：

maxValue = previousValues[position+1]

你的代码允许查看前一行中的三个不同的总和，但它只应该查看两个（最多）：在position-1处的一个（如果有效），以及在position处的一个，而不是在position+1处的一个。

- trincot

Answer 2

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

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

- Thomson Mixab

---

确实，但是练习题说的不一样。
maximumPathSumI(testTriangle) 应该返回一个数字。
maximumPathSumI(testTriangle) 应该返回23。
maximumPathSumI(numTriangle) 应该返回1074。 - baloo