Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Подматрица с максимальной суммой
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Есть матрица N*M состоящая из целых чисел. Требуется найти в ней прямоугольную подматрицу с максимальной суммой чисел.
Понятно как решить ее за O(N*M*M), но можно ли быстрее? Если нельзя в общем, то может можно для каких-то частных случаев?
Можно за O(n^2*log(n)), если в ней n ненулевых элементов, с помощью веселого дерева отрезков
Можно поподробнее?
В общем случае вероятно нельзя
1717 решается например так:
Посортить вершины по x, перебрать левую границу прямоугольника x1, внутри завести дерево отрезков по y, где в каждой вершине для подотрезка хранить: сумму функций на отрезке, сумму на лучшем подотрезке, сумму лучшего подотрезка начинающегося в левой границе и заканчивающегося раньше правой, сумму лучшего подотрезка начинающегося раньше правой границы и заканчивающегося в ней, последнее 2 отдельно для 1 и >= 2 команд. После того как выбрали левую границу и завели дерево надо по очереди делать следующее: прорелаксировать все вершины с первым нерассмотренным x >= x1, узнать ответ (лучший подотрезок корня для >= 2 команд).
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Подматрица с максимальной суммой