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

最大のサブマトリックスです（長方形の場合もあります）。thisはあなたに役立つかもしれません。行列に対してkadaneのアルゴリズムを使用すると、O(n^3)で行うことができます。