Тема: Прямоугольник
Задан целочисленный прямоугольный массив MxN. Необходимо определить прямоугольную область данного массива, сумма элементов которого максимальна. Кто сможет решить задачу за O(MN) или за O(MNMN)
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Прямоугольник
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Задан целочисленный прямоугольный массив MxN. Необходимо определить прямоугольную область данного массива, сумма элементов которого максимальна. Кто сможет решить задачу за O(MN) или за O(MNMN)
Ну за 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).
если задан прямоугольный массив MxN, это ведь и есть прямоугольная область(ПО) данного массива?
тогда ответом будет ПО MXN? а сумму можно найти за O(MN)!
Числа в матрице могут быть отрицательными.
Т.о. не всегда лучшим ответом будет являться вся область матрицы.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Прямоугольник