|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexey Kruglov 2:5015/70.5 26 Apr 2002 22:56:58
To : Serg Belyaev
Subject : Максимальная сумма
--------------------------------------------------------------------------------
Четверг 25 Апреля 2002 23:25, Serg Belyaev wrote to All:
SB> Вот попалась интересная задачка 108 (acm.gui.uva.es/problemset)
SB> Дан 2-мерный массив положительных и отрицательных целых чисел,
SB> найти подпрямоугольник с наибольшей суммой. Сумма прямоугольника
SB> это сумма всех элементов этого прямоугольника.
Есть решение за \Theta(m^2 n), где mxn -- размеры прямоугольника. У тебя,
кстати, нет ограничений, так что подошло бы и решение в лоб за \Theta((mn)^3).
Перебираем вертикальный размер k подпрямоугольника. Для каждого k строим
матрицу, (i,j)-ый элемент = сумме прямоугольника kx1 с левой верхней клеткой в
(i,j). При увеличении k на 1 эту матрицу можно обновить за O(mn). В ней надо
найти подпрямоугольник высоты 1 с max суммой. Это можно сделать для каждой
строки отдельно.
Пусть a_1, ... , a_n -- эта строка. b_i:=-\sum_{j=i}^n a_i. Тогда надо найти
x<=y: b_y-b_x максимально; решением будет прямоугольник ширины (y-x) от x до
(y-1). Для этого кандидата в x-ы изменяем от n до 1. При каждом x:
b_y=max_{y'>=x} b_{y'}, т.к., если x фиксирован, b_y должен быть максимальным.
b_x и b_y обновляются за O(1) => для матрицы это делается за O(mn). Берем
максимум по x, потом по строкам, потом по k и получаем ответ.
SB> Пример:
SB> 0 -2 -7 0
SB> 9 2 -6 2
SB> -4 1 -4 1
SB> -1 8 0 -2
SB> тогда подпрямоугольник с максимальной суммой:
SB> 9 2
SB> -4 1
SB> -1 8
SB> и сумма равна 15.
Пример того, что делается в последнем абзаце для k=3, вторая строка моей
вспомогательной матрицы.
a=(4, 11, -10, 1)
0. x=5; b_x:=0; b_y:=0; y:=5. b_y-b_x=0.
1. x=4; b_x:=b_x-a_x=-1; b_y:=max(b_y,b_x)=0. b_y-b_x=1.
2. x=3; b_x:=-1-(-10)=9; b_y:=max(0,9)=9 => y:=3. b_y-b_x=0.
3. x=2; b_x:=9-11=-2; b_y:=max(9,-2)=9. b_y-b_x=11.
4. x=1; b_x:=-2-4=-6; b_y:=max(9,-6)=9. b_y-b_x=15.
Получается max суммы для (k=2, прямоугольник со 2-ой строки) = 15 при x=1; y=3,
т.е. прямоугольник ширины 2 с колонки 1 по 2.
nOkA. Alexey.
--- GoldED+/386 1.1.4.7
* Origin: 6DFA 1186 7576 DE60 6CCB EB39 AD81 1733 EEBB 970A (2:5015/70.5)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Максимальная сумма 
