Непрерывный блок All-one в матрице

Question

Предположим, вам дано растровое изображение mXn, представленное массивом M [1..m, 1 .. n], все записи которого равны 0 или 1. Блок все-один - это подрешетка вида M [i.. i0, j .. j0], в котором каждый бит равен 1. Опишите и проанализируйте эффективный алгоритм, чтобы найти единичный блок в M с максимальной площадью

Я пытаюсь найти решение для динамического программирования,Но мой рекурсивный алгоритм выполняется за O (n ^ n) времени, и даже после запоминания я не могу думать о его снижении ниже O (n ^ 4).Может кто-нибудь помочь мне найти более эффективное решение?

Answer 1

Это всего лишь идея, и я не уверен, что она работает.

Определите A (i, j) (di, dj) как единичный блок из (i, j) в (i + di, j + dj), что означает M [x, y] = 1 для i <= x <= i + di и j <= y <= j + dj. </p>

Определите A (i, j) (di, dj) как max-block , если не удерживаются A (i, j) (di + 1, dj) и A (i, j ) (ди, ди-джей + 1).

Для каждого (i, j) мы можем составить список, назовем его L (i, j) из max-блоков. Максимальная длина списка min (m-i + 1, n-j + 1) <= min (m, n). </p>

L (i, j) зависит только от M [i, j], L (i + 1, j) и L (i, j + 1). Я думаю, что построение L (i, j) из L (i + 1, j) и L (i, j + 1) может быть сделано за линейное время, это напоминает мне о слиянии отсортированных списков. С помощью L (i, j) найдите max (di * dj) для A (i, j) (di, dj) в L (i, j). Максимальное из этих значений указывает максимальный блок all-one.

Этот подход имеет сложность n * m * min (m, n) ~ = n ^ 3 и требует min (m, n) ^ 2 места для хранения последних 2 строк, которые необходимы.