Получить координаты самой большой подматрицы

Question

У меня самая большая подматрица m1 x n1 подматрицы m x n. Я нашел, как максимальная сумма подматрицы, но я хотел бы знать, как найти координаты в r1c1 (первая строка и первый столбец этой подматрицы) и r2c2 (последняя строка и последний столбец этой подматрицы).

ТакПока у меня есть предварительно обработанная матрица, которая хранит свои суммы в каждом элементе, как в:

SUM[i, j] = SUM[i−1, j] + SUM[i, j−1] − SUM[i−1, i−1] + MATRIX[i, j]

Я обнаружил, что для любого заданного r1, c1, r2, c2:

SUMS = SUM[r2,c2] - SUM[r1-1,c2] - SUM[r2,s1-1] + SUM[r1-1,c2-1]

Как мне подойти к этой проблеме, если я хочу получить вывод, который мог бы сообщить мне координаты этой подматрицы?

Answer 1

Вы можете перебрать все возможные r1 и r2, затем снова можете перебрать все возможные c1 и c2 для этой пары r1, r2 и рассчитать сумму этой подматрицы по вашей SUMмассив, это прямо вперед, но не эффективно.

Сложность времени O (м ² n ² )

---

Давайте попробуем улучшить ее. Вы можете узнать сумму от r1 до r2 для каждого столбца за O(1) времени, выполнив некоторую предварительную обработку. Таким образом, мы превращаем самую большую двумерную проблему подматрицы в 1D Максимальную проблему подмассива , которая может помочь нам найти c1 и c2 для этой пары r1, r2 за O(n) времени.

Временная сложность O (мн ² )