求SubMatrix 3x3 JavaScript的最大和

Question

我用矩阵练习工作，但我被困在这里。我需要找到subMatrix的最大和。

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

​

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

Answer 2

您可以使用reduce方法创建一个函数，该函数接受col和row params，并将它们从原始数组中切片，但是对于内部数组，只需反转元素顺序即可。

​

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, 11, 40],
]

function sum(matrix, row, col) {
  return matrix.slice(0, row).reduce((r, e) => {
    [...e].reverse().slice(0, col).forEach(c => r += c)
    return r;
  }, 0)
}

console.log(sum(matrix, 3, 3))

​

或者，您可以从内部数组的末尾切片，再使用一次精简。

​

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, 11, 40],
]

function sum(matrix, row, col) {
  return matrix.slice(0, row).reduce((r, e) => {
    return r + e.slice(-col).reduce((a, c) => a + c, 0)
  }, 0)
}

console.log(sum(matrix, 3, 3))

​

Answer 3

你可以先得到矩阵的一部分，然后得到子矩阵的和。

​

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, 11, 40]],
    cols = 3,
    rows = 3,
    left = -3,
    top_ = 0,                                   // top is a reserved property of windows
    sum = matrix
        .slice(top_, top_ >= 0 ? rows : undefined)
        .map(a => a.slice(left, left >= 0 ? cols : undefined))
        .reduce((r, a) => a.reduce((s, v) => s + v, r), 0);

console.log(sum);

​