задачка с acm.uva.es :)

From

Alexey Burdin (2:5012/2.89)

To

Grebnov Ilya

Date

2002-12-22T22:40:21Z

Area

RU.ALGORITHMS

> from: /Unknown/
Как после вчерашнего, Grebnov ?

 19:35 Вторник Декабрь 10 2002, Grebnov Ilya --> ALL:

 AB>> Дана матpица 100х100 (ну или меньше) целых чисел от -127 до
 AB>> 127. Необходимо найти в ней такой пpямоугольник, чтобы сумма
 AB>> всех чисел в нем была максимальна (из всех возможных
 AB>> таких пpямоугольников).

 GI>   Вот мое pешение. Сложность O(n^3). Кpитика пpиветствуется!
 GI>                             РЕШЕНИЕ.
    [поскипано]
    Критика 1. Алгоритм неверно работает при всех отрицательных числах
    в матрице (выдаёт 0).
    Критика 2. (Относится также к Илье Кантору) Ты хочешь найти (самым
    вложенным циклом) подпоследовательность с максимальной суммой за O(N)
    действий. Имхо это невозможно. Наилучший метод за O(N*logN), заключается
    в составлении последовательности сумм (s[1]=a[1], s[j]=s[j-1]+a[j]), её
    быстрой сортировке и нахождению максимальной разности между этими суммами
    с учетом того, что бОльшая сумма должна быть с бОльшим индексом.

    Илья Кантор так и не пояснил насчет "простого сканирующего алгоритма".

                Всего хорошего. Alexey.
... А что подyмал кpолик, никто не yзнал,
--- потомy что кpолик был очень воспитанный.
 * Origin: Wishful goddess, at night (2:5012/2.89)