如何计算矩阵的子矩阵

Question

我正在为一家名为 Code Nation 的公司进行测试，并遇到了这个问题，该问题要求我计算数字 k 在子矩阵 M[n][n] 中出现了多少次。现在有一个例子说 Input like this.

5
1 2 3 2 5
36

M[i][j]是由a[i]*a[j]计算出来的在计算轮到我可以计算。

1,2,3,2,5
2,4,6,4,10
3,6,9,6,15
2,4,6,4,10
5,10,15,10,25

现在我必须计算36在M的子矩阵中出现了多少次

答案是 5。

我无法理解如何计算这个子矩阵。如何表示？ 我有一个天真的方法，导致许多我认为 none 是正确的矩阵。

其中一个是Submatrix[i][j]

1 2 3  2  5
3 9 18 24 39
6 18 36 60 99
15 33 69 129 228
33 66 129 258 486

这是把0,0之前的所有数字加到i,j上得到的

在这个 36 中没有出现 5 次所以我知道这是不正确的。如果你能用一些伪代码来支持它，那将是锦上添花。

感谢帮助

[编辑] : 参考 link 1 link 2

Answer 1

我的猜测是，您必须计算 M 的子矩阵中有多少个子矩阵的和等于 36。

这是 Matlab 代码：

a=[1,2,3,2,5];
n=length(a);
M=a'*a;
count = 0;
for a0 = 1:n
    for b0 = 1:n
        for a1 = a0:n
            for b1 = b0:n
                A = M(a0:a1,b0:b1);
                if (sum(A(:))==36)
                    count = count + 1;
                end
            end
        end
    end
end
count

这会打印出 5。

所以你正确计算了M，但是你必须考虑M的每个子矩阵，例如M是

1,2,3,2,5
2,4,6,4,10
3,6,9,6,15
2,4,6,4,10
5,10,15,10,25

所以一种可能的子矩阵是

1,2,3
2,4,6
3,6,9

如果将所有这些加起来，则总和等于 36。

有一个 answer on cstheory 给出了 O(n^3) 算法。

如何计算矩阵的子矩阵

How to calculate Sub matrix of a matrix

algorithm

submatrix