0

私は正方形のボード（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++;
    }
}

しかし、これが正しい方法かどうかはわかりません。何かご意見は？

4

1 に答える 1

0

最大の部分行列、つまり、長方形にすることもできます。これが役立つ場合があります。行列に kadane のアルゴリズムを使用すると、 で実行できますO(n^3)。

于 2012-04-05T00:55:19.203 に答える