java - 迭代 NxN 矩阵的所有子矩阵的最佳/最快方法

Question

我有一个方板（NxN 矩阵）。每个正方形（单元格）都有与其相关的特定点。我的目标是找到具有最高点总和的最大子矩阵。我开始尝试找到所有子矩阵及其权重。但我被困在如何去做这件事上。

我想我可以有一个HashMap<String,Integer>存储初始行、列和子矩阵的大小。代码应如下所示：

int [][] mat = new int[10][10];

void countSubMatrix()
{
    for(int i = 0; i<mat.length; i++)
    {
        for(int j = 0; j<mat[i].length; j++)
        {
            storeSubMatrix(i,j);
        }
    }
}

void storeSubMatrix(int x, int y)
{
    int size = 0;
    int tempX = x;
    int tempY = y;
    while(tempX < board.length && tempY < board[x].length)
    {
        map.put(x.toString() + "," + y.toString(),size+1);
        tempX++;
        tempY++;
    }
}

但我不知道这是否是正确的方法。有什么想法吗？

Answer 1

最大的子矩阵，即它也可以是一个矩形，那么这可能对你有帮助。使用 kadane 的矩阵算法可以在O(n^3).