1

Тема: Прямоугольник

Задан целочисленный прямоугольный массив MxN. Необходимо определить прямоугольную область данного массива, сумма элементов которого максимальна. Кто сможет решить задачу за O(MN) или за O(MNMN)

2

Re: Прямоугольник

Ну за O(MNMN) понятно как, перебираем пары противоположных углов, считаем сумму элементов за O(1) и выбираем максимум, чтобы считать сумму элементов нужно предрасчет сделать за O(MN) -- посчитать s(i, j) - сумма элементов в прямоугольнике (1, 1) - (i, j). Из этого не сложно за O(1) получить сумму в произвольном прямоугольнике.

За O(MN) наврядли можно.

За O(MMN) можно решить.
Можно решать такую задачу за O(N) -- есть N элементов, нужно найти подпоследовательность (подряд идущих элементов), что их сумма максимальна.
Зафиксируем какие-то две строки ( O(MM) ) -- горизонтальные границы нашего возможного прямоугольника, и вместо каждого столбца запишем сумму элементов в нем в этих горизонтальных границах, тогда у нас получится предыдущая задача, которую можно решить за O(N).

3

Re: Прямоугольник

если задан прямоугольный массив MxN, это ведь и есть прямоугольная область(ПО) данного массива?
тогда ответом будет ПО  MXN? а сумму можно найти за O(MN)!

4

Re: Прямоугольник

Числа в матрице могут быть отрицательными.
Т.о. не всегда лучшим ответом будет являться вся область матрицы.