Somme maximale de toutes les sous-matrices principales

Question

Le problème est donné dans le titre. Mon approche de ce problème est comme ça:

1. Créer une matrice binaire B où 1s représente les nombres premiers dans l'entrée laisser dire V, qui est la matrice nxn entier non négatif
2. Trouver toutes les sous-matrices positives, y compris 1x1 fom B
3. Trouvez la somme d'entre eux et renvoyez la plus grande avec le coin supérieur gauche de la sous-matrice et sa taille.

Dans ce sens, la section 2 de mon algorithme semble un peu compliquée. Y at-il un moyen de les trouver sans la force brute, qui est je pense, en itérant via des boucles et de les trouver. J'espère que matlab a une fonction qui retourne ce que je veux.

Toute aide est appréciée.

Answer 1

c'est à peu près ce que vous avez prévu:

% 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