Re: Максимальная сумма

From

Sergey Andrianov (2:5020/1507.400)

To

Serg Belyaev

Date

2002-05-03T13:32:14Z

Area

RU.ALGORITHMS

Здравствуй, Serg!

Однажды 25-Apr-02  в 23:25   Serg Belyaev (2:5015/166.7)
написал       All    по поводу
-=-   Максимальная сумма  -=-

SB> Вот попалась интересная задачка 108 (acm.gui.uva.es/problemset)

SB> Дан 2-мерный массив положительных и отрицательных целых чисел,
SB> найти подпрямоугольник с наибольшей суммой. Сумма прямоугольника
SB> это сумма всех элементов этого прямоугольника.
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.

   1. Можно решать влоб, тогда при размере массива M*N и прямоугольника L*K временнАя сложность будет M*N*L*K. 
   2. Можно применить скользящее окно, тогда вместо вычисления суммы L*K на каждом шаге берется один раз вычисленная, а затем по мере прдвижения от нее вычитается тот столбец (строка), который "покинул" прямоугольник, и прибавляется тот, который "вошел" в него. Сложность порядка M*N*min(L+K).
   3. Дальнейшее уменьшение сложности можно сделать при выделении дополнительной памяти: Сначала выделяем массив шириной (M-L+1) и высотой N. В каждую ячейку массива записываем сумму подстроки длиной L, которую вычисляем из предыдущей путем добавления и вычитания по одному числу (опять скользящим окном). Сложность этого этапа M*N. Дальше выделяем второй массив такой же ширины и высотой (N-K+1). В него аналогично записываем суммы по столбцам. Сложность (M-L+1)*N. Эти суммы по столбцам и есть суммы в прямоугольнике, можно сразу искать максимум. Итого, сложность M*N.


                  До свидания,  в  13:21 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)