时间戳

首页 > 解决方案 > 在二维数组/矩阵中查找最大和子矩阵

javascript - 在二维数组/矩阵中查找最大和子矩阵

问题描述

请在下面找到我当前的实现：

function findMaxSumSubMatrix(matrix) {
    var dim = matrix[0].length;

    // initialize prefix sum matrix
    var ps = new Array();
    for (var _ = 0; _ < dim; _++) {
        ps[_] = new Array();
    }

    // calculate vertical prefix sum matrix
    for (var i = 0; i < dim; i++) {
        for (var j = 0; j < dim; j++) {
            if (j == 0) {
                ps[j][i] = matrix[j][i];
            } else {
                ps[j][i] = matrix[j][i] + ps[j - 1][i];
            }
        }
    }

    // console.log(ps); // log prefix sum matrix

    var maxSum = 0;
    var min, temp;

    // using the prefix sum matrix, iterate over all combinations and keep track of the max (Kadane's algorithm)
    for (var i = 0; i < dim; i++) {
        for (var j = i; j < dim; j++) {
            min = 0;
            temp = 0;
            for (var k = 0; k < dim; k++) {
                if (i == 0) {
                    temp += ps[j][k];
                } else {
                    temp += ps[j][k] - ps[i - 1][k];
                }

                if (temp < min) {
                    min = temp;
                }

                if (temp - min > maxSum) {
                    maxSum = temp - min;
                }
            }
        }
    }

    return maxSum;
}


var example1 = [
    [1, -61, 5126, 612, 6],
    [41, 6, 7, 2, -7],
    [1, 73, -62, 678, 1],
    [7, -616136, 61, -83, 724],
    [-151, 6247, 872, 2517, 8135],
];

console.log(findMaxSumSubMatrix(example1)); // expected output: 18589

这按预期工作，输出是正确的。

但是，我并没有完全自己编写代码。

我不清楚的是“min”和这部分：

if (temp < min) {
    min = temp;
}

if (temp - min > maxSum) {
    maxSum = temp - min;
}

有人可以向我解释那里发生了什么，以及为什么需要它吗？我尝试省略它，给出不正确的结果。

谢谢你。

标签： javascriptalgorithmmatrix

解决方案

将其视为一个简单的一维数组，您必须在其中找到最大的连续子序列和（正是 Kadane 算法所做的）。对于每个前缀总和，您将考虑其前面的最低前缀总和并计算差异（选择最低的，因为您需要最大化差异）。

同样，这里的二维数组也存储了前缀和。我们用来min跟踪当前列中遇到的最低总和。由于我们需要最大和，我们尝试最大化当前前缀和（即temp）与遇到的最小和（即 ）之间的差异min。

推荐阅读