Найти максимальную сумму JavaScript SubMatrix 3x3

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. Мне нужно найти maxSum из 3x3 подматриц. Таким образом, 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

Скрипт должен работать с большей матрицей. Мне нужна помощь, я не могу заставить ее итерацию правильно для каждой матрицы 3х3.

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

Вы можете создать функцию с методом reduce, которая будет принимать параметры столбцов и строк и вырезать их из исходных массивов, но для внутреннего массива вы просто меняете порядок элементов в обратном порядке.

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 2

Вы можете сначала получить часть матрицы, а затем получить сумму подматрицы.

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

Answer 3

Будет проще, если вы замените свой внешний цикл двумя внешними циклами: один для того, что будет в первом ряду подматрицы, и другой для его первого столбца.Затем два внутренних цикла должны перебрать 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));

Конечно, есть более краткие способы кодирования, но я решил придерживаться шаблонов, которые вы уже пытались использовать.