Ну за 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).
причем стабильно, где много латекса