CODEWITHSUNDEEP
javaalgorithmmatrix
noMAD
noMAD

Reputation: 7844

Best/Fastest way to iterate through all sub-matrices of a NxN matrix

I have a square board (NxN matrix). Each square (cell) has a certain points associated to it. My goal is to find the largest sub-matrix which has the highest summation of points. I started off with trying to find all the sub-matrices and their weights. But I am stuck on how to go about doing it.

I thought I could have a HashMap<String,Integer> which stores the initial row,column and the size of the sub matrix. The code should look something like this:

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++;
    }
}

But I don't know if this is the right way to do it. Any thoughts?

Upvotes: 0

Views: 3379

Answers (1)

Priyank Bhatnagar
Priyank Bhatnagar

Reputation: 814

Largest submatrix ,i.e, it can also be a rectangle, then this might be of help to you. Using kadane's algorithm for matrix it can be done in O(n^3).

Upvotes: 0

Related Questions