Вот алгоритм O(numCols*numLines^2). Пусть S[i][j] = sum of the first i elements of column j.
Я буду работать алгоритм на этом примере:
M
1 1 0 0 1 0
0 1 1 1 0 1
1 1 1 1 0 0
0 0 1 1 0 0
У нас есть:
S
1 1 0 0 1 0
1 2 1 1 1 1
2 3 2 2 1 1
2 3 3 3 1 1
Теперь рассмотрим задачу нахождения максимального подмассива всех единиц в одномерном массиве. Это можно решить с помощью этого простого алгоритма:
append 0 to the end of your array
max = 0, temp = 0
for i = 1 to array.size do
if array[i] = 1 then
++temp
else
if temp > max then
max = temp
temp = 0
Например, если у вас есть этот 1d массив:
1 2 3 4 5 6
1 1 0 1 1 1
вы бы сделали это:
Первое добавление 0:
1 2 3 4 5 6 7
1 1 0 1 1 1 0
Теперь обратите внимание, что всякий раз, когда вы нажимаете 0, вы знаете, где заканчивается последовательность смежных. Поэтому, если вы сохраняете промежуточную сумму (переменная temp) текущего числа единиц, вы можете сравнить эту сумму с максимальным значением (переменная max), когда вы достигнете нуля, а затем сбросить промежуточную сумму. Это даст вам максимальную длину непрерывной последовательности единиц в переменной max.
Теперь вы можете использовать этот подалгоритм, чтобы найти решение вашей проблемы. Прежде всего добавьте столбец 0 к вашей матрице. Затем вычислите S.
Тогда:
max = 0
for i = 1 to M.numLines do
for j = i to M.numLines do
temp = 0
for k = 1 to M.numCols do
if S[j][k] - S[i-1][k] = j - i + 1 then
temp += j - i + 1
else
if temp > max then
max = temp
temp = 0
По сути, для каждой возможной высоты подмассива (имеется O(numLines^2) возможных высот) вы находите объект с максимальной площадью, имеющей эту высоту, применяя алгоритм для одномерного массива (в O(numCols)).
Рассмотрим следующую «картинку»:
M
1 1 0 0 1 0 0
i 0 1 1 1 0 1 0
j 1 1 1 1 0 0 0
0 0 1 1 0 0 0
Это означает, что у нас фиксированная высота j - i + 1. Теперь возьмем все элементы матрицы, которые находятся между i и j включительно:
0 1 1 1 0 1 0
1 1 1 1 0 0 0
Обратите внимание, что это похоже на одномерную проблему. Давайте сложим столбцы и посмотрим, что мы получим:
1 2 2 2 0 1 0
Теперь задача сводится к одномерному случаю, за исключением того, что мы должны найти подпоследовательность смежных j - i + 1 (в данном случае 2) значений. Это означает, что каждый столбец в нашем j - i + 1 "окне" должен быть полон единиц. Мы можем проверить это эффективно, используя матрицу S.
Чтобы понять, как работает S, еще раз рассмотрим одномерный случай: пусть s[i] = sum of the first i elements of the vector a. Тогда какова сумма подпоследовательности a[i..j]? Это сумма всех элементов до a[j] включительно, минус сумма всех элементов до a[i-1] включительно, что означает s[j] - s[i-1]. Случай 2d работает так же, за исключением того, что у нас есть s для каждого столбца.
Надеюсь, это понятно, если у вас есть еще вопросы, пожалуйста, задавайте.
Я не знаю, подходит ли это вам, но я думаю, что есть также алгоритм O(numLines*numCols), основанный на динамическом программировании. Я пока не могу понять, за исключением случая, когда искомый вами массив является квадратным. У кого-то может быть лучшее понимание, поэтому подождите немного больше.