所有素数子矩阵的最大总和

Question

问题在标题中给出。我对这个问题的办法是这样的：

1. 创建一个二进制矩阵B，其中1S表示输入的素数让说V，这是n×n的非负整数矩阵的
2. 找到所有的正子矩阵包括1×1 f B
3. 找到它们的总和，并返回最大的一个与子矩阵的左上角和它的大小。

从这个意义上说，我的算法的第2部分看起来有点复杂。有没有什么办法可以在没有暴力的情况下找到它们，我认为这是通过循环迭代并找到它们。我希望matlab有一个函数返回我想要的。

任何帮助表示赞赏。

Answer 1

这大约是你的计划是什么：

% generate random matrix 
sz = [20 20]; 
imax = 200; 
A = randi(imax,sz); 
% binary matrix of primes 
B = isprime(A); 
% concat both 
C = cat(3,A,B); 
% compute maximum number of rows&cols in each cc in B 
cc = bwconncomp(B,4); 
[rows,cols] = cellfun(@(ind)ind2sub(size(B),ind),cc.PixelIdxList,'UniformOutput',false); 
maxwidth = max(cellfun(@(c) max(c) - min(c),cols)) + 1; 
maxheight = max(cellfun(@(c) max(c) - min(c),rows)) + 1; 
% find max-sum sub matrix 
valMax = 0; 
idxMax = [0,0]; 
for ii = 1:maxheight 
    for jj = 1:maxwidth 
     % generate rectangle filter 
     h = ones(ii,jj); 
     n1 = ii*jj; % number of elements in filter 
     % filter the concat matrix 
     res = imfilter(C,h); 
     % indexes of cc having rectangular shape 
     idxs = find(res(:,:,2) == n1); 
     if isempty(idxs) 
      break 
     end 
     % find max value of all relevant rectangles 
     [v,i] = max(res(idxs)); 
     if v > valMax 
      valMax = v; % max value 
      [r,c] = ind2sub(size(B),idxs(i)); 
      r = r - ceil(ii/2) + 1; 
      c = c - ceil(jj/2) + 1; 
      idxMax = [c,r,jj,ii]; % max value rect [x,y,w,h] 
     end 
    end 
end