На этот вопрос я уже ответил здесь (и здесь , измененная версия). В обоих случаях алгоритм был применен к двоичному случаю (нулям и единицам), но модификация для произвольных чисел довольно проста (но извините, Я сохраняю изображения для двоичной версии задачи ). Вы можете сделать это очень эффективно с помощью двухпроцессорного алгоритма linear O(n) time - n равно числу элементов. Тем не менее, это не динамическое программирование - я думаю, что использование динамического программирования здесь было бы неуклюжим и неэффективным в конце концов, из-за трудностей с декомпозицией проблемы, как упоминалось в OP - если только это не домашнее задание - но в этом случае вы можете попытаться впечатлите этим алгоритмом :-), поскольку, очевидно, нет более быстрого решения, чем O(n).
Алгоритм (изображения изображают двоичный регистр) :
Допустим, вы хотите найти самый большой прямоугольник из свободных (белых) элементов.
Здесь следует алгоритм двухпроходного линейного O(n) времени (n - количество элементов):
1) в первом проходе , пройти по столбцам снизу вверх, и для каждого элемента обозначить количество последовательных элементов, доступных до этого:
повтор, до:
Картинки изображают двоичный регистр. В случае произвольных чисел вы держите 2 матрицы - сначала с исходными числами, а затем с вспомогательными числами, которые заполнены на рисунке выше. Вы должны проверить исходную матрицу, и если вы найдете число, отличное от предыдущего, вы просто начнете нумерацию (во вспомогательной матрице) снова с 1.
2) во втором проходе вы идете по строкам, хранящим структуру данных потенциальных прямоугольников, то есть прямоугольников, содержащих текущую позицию где-то у верхнего края. Смотрите следующее изображение (текущая позиция красного цвета, 3 потенциальных прямоугольника - фиолетовый - высота 1, зеленый - высота 2 и желтый - высота 3):
Для каждого прямоугольника мы сохраняем его высоту k и его левый край. Другими словами, мы отслеживаем суммы последовательных чисел, которые были >= k (то есть потенциальные прямоугольники высотой k). Эта структура данных может быть представлена массивом с двойным связанным списком, связывающим занятые элементы, а размер массива будет ограничен высотой матрицы.
Псевдокод 2-го прохода (недвоичная версия с произвольными числами):
var m[] // original matrix
var aux[] // auxiliary matrix filled in the 1st pass
var rect[] // array of potential rectangles, indexed by their height
// the occupied items are also linked in double linked list,
// ordered by height
foreach row = 1..N // go by rows
foreach col = 1..M
if (col > 1 AND m[row, col] != m[row, col - 1]) // new number
close_potential_rectangles_higher_than(0); // close all rectangles
height = aux[row, col] // maximal height possible at current position
if (!rect[height]) { // rectangle with height does not exist
create rect[height] // open new rectangle
if (rect[height].next) // rectangle with nearest higher height
// if it exists, start from its left edge
rect[height].left_col = rect[height].next.left_col
else
rect[height].left_col = col;
}
close_potential_rectangles_higher_than(height)
end for // end row
close_potential_rectangles_higher_than(0);
// end of row -> close all rect., supposing col is M+1 now!
end for // end matrix
Функция для закрытия прямоугольников:
function close_potential_rectangles_higher_than(height)
close_r = rectangle with highest height (last item in dll)
while (close_r.height > height) { // higher? close it
area = close_r.height * (col - close_r.left_col)
if (area > max_area) { // we have maximal rectangle!
max_area = area
max_topleft = [row, close_r.left_col]
max_bottomright = [row + height - 1, col - 1]
}
close_r = close_r.prev
// remove the rectangle close_r from the double linked list
}
end function
Таким образом, вы также можете получить все максимальные прямоугольники. В итоге вы получите:
А какая сложность будет? Вы видите, что функция close_potential_rectangles_higher_than равна O(1) на замкнутый прямоугольник. Поскольку для каждого поля мы создаем 1 потенциальный прямоугольник в максимуме, общее количество потенциальных прямоугольников, когда-либо присутствующих в конкретной строке, никогда не превышает длину строки. Поэтому сложность этой функции O(1) амортизируется!
Таким образом, вся сложность равна O(n), где n - количество элементов матрицы.