javascript - 求 SubMatrix 3x3 JavaScript 的最大和

Question

我练习使用矩阵，但我坚持在这里。我需要找到子矩阵的最大和。

const matrix = [ 
    [ 1,  1,  3,  3,  5],
    [-6, -7,  2, -3, -1],
    [ 3,  0, -4,  5,  9],
    [ 7, -7,  0,  1,  0],
    [-7, -6, -4, -4,  9],
]

当前矩阵为 5x5。我需要找到 3x3 子矩阵的 maxSum。所以这里的 maxSum 是 19。我在这里突出显示具有这个总和的子矩阵:

            +----------+
     1   1  |  3  3  5 | 
    -6  -7  |  2 -3 -1 | 
     3   0  | -4  5  9 | 
            +----------+
     7  -7     0  1  0
    -7  -6    -4 -4  9

该脚本应该适用于更大的矩阵。我需要帮助，我无法让它在每个 3x3 矩阵上正确迭代。

const subLength = 3 * 3;
let maxSum = 0;
for (let subMatrix = 0; subMatrix < subLength; subMatrix++) {
    let sum = 0;
    for (let rows = 0; rows < 3; rows++) {
        for (let cols = subMatrix; cols < matrix.length; cols++) {
            sum += matrix[rows][cols];
        }
    }
    if (maxSum < sum) {
        maxSum = sum;
    }
}
console.log(maxSum);

该代码适用于该矩阵，但不适用于另一个矩阵，我知道问题出在第三个嵌套循环中，也可能出现在第一个嵌套循环中。在第三个中，我必须从 0 迭代到 3，然后从 1 迭代到 (3 + 1)，从 (3 + 2) 迭代，然后移动到第二行的下一个数组，并再次从零开始。

你能修复我的代码吗？

Answer 1

如果用两个外循环替换外循环会更容易:一个用于子矩阵的第一行，另一个用于子矩阵的第一列。然后两个内部循环应该迭代从那里开始的子矩阵的 3 行和 3 列。

这是您的代码，只需进行最少的更改:

function maxSubSum(matrix, subLength) {
    let maxSum = 0;

    for (let firstRow = 0; firstRow <= matrix.length - subLength; firstRow++) {
        for (let firstCol = 0; firstCol <= matrix[0].length - subLength; firstCol++) {
            let sum = 0;
            for (let row = 0; row < 3; row++) {
                for (let col = 0; col < 3; col++) {
                    sum += matrix[firstRow+row][firstCol+col];
                }
            }
            if (maxSum < sum) {
                maxSum = sum;
            }
        }
    }
    return maxSum;
}

const matrix = [ 
    [ 1,  1,  3,  3,  5],
    [-6, -7,  2, -3, -1],
    [ 3,  0, -4,  5,  9],
    [ 7, -7,  0,  1,  0],
    [-7, -6, -4, -4,  9],
];

console.log(maxSubSum(matrix, 3));

当然有更简洁的方法来编码，但我决定坚持使用您已经尝试使用的模式。