所有素數子矩陣的最大總和

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