Лучший/Самый быстрый способ перебора всех подматриц матрицы 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 может вам помочь. Используя алгоритм Кадана для матрицы, это можно сделать в O(n^3).