|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serg Belyaev 2:5015/166.7 28 Apr 2002 23:02:06
To : Alexey Kruglov
Subject : Максимальная сумма
--------------------------------------------------------------------------------
SB>> Дан 2-мерный массив положительных и отрицательных целых чисел,
SB>> найти подпрямоугольник с наибольшей суммой. Сумма прямоугольника
SB>> это сумма всех элементов этого прямоугольника.
AK> Есть решение за \Theta(m^2 n), где mxn -- размеры прямоугольника. У тебя,
AK> кстати, нет ограничений, так что подошло бы и решение в лоб за
AK> \Theta((mn)^3).
Hу, скажем, очевидное решение имеет сложность O((mn)^2) :)
AK> Перебираем вертикальный размер k подпрямоугольника. Для каждого k строим
AK> матрицу, (i,j)-ый элемент = сумме прямоугольника kx1 с левой верхней
AK> клеткой в
AK> (i,j). При увеличении k на 1 эту матрицу можно обновить за O(mn). В ней
AK> надо
AK> найти подпрямоугольник высоты 1 с max суммой. Это можно сделать для
AK> каждой
AK> строки отдельно.
AK> Пусть a_1, ... , a_n -- эта строка. b_i:=-\sum_{j=i}^n a_i. Тогда
AK> надо найти x<=y: b_y-b_x максимально; решением будет прямоугольник
AK> ширины (y-x) от x до (y-1). Для этого кандидата в x-ы изменяем
AK> от n до 1. При каждом x:
AK> b_y=max_{y'>=x} b_{y'}, т.к., если x фиксирован, b_y должен быть
^^^^^^^^^^^за O(n), да еще пробег по x,
т.е. получается, что для поиска x,y требуется O(n^2) операций - плохо.
AK> максимальным.
AK> b_x и b_y обновляются за O(1) => для матрицы это делается за O(mn). Берем
AK> максимум по x, потом по строкам, потом по k и получаем ответ.
Одномерный случай (поиск подпоследовательности с максимальной
суммой) известен, как головоломка Давида Гриса - сложность O(n),-
делается за один проход.
Тогда основная задача решается за O(n^3) операций (n=m).
Можно ли сделать быстрее? Hаверное - нет, но вопрос открыт.
Всего доброго,
<SVB> (Serg Belyaev)
--- Terminate 5.00/Pro
* Origin: (svb@sandy.ru) or (2:5015/166.7)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Максимальная сумма