|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5020/1507.400 03 May 2002 13:32:14
To : Serg Belyaev
Subject : Re: Максимальная сумма
--------------------------------------------------------------------------------
Однажды 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
