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

From

Alexey Burdin (2:5012/2.89)

To

Alex Cvetkov

Date

2002-12-22T22:52:45Z

Area

RU.ALGORITHMS

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

 11:51 Вторник Декабрь 10 2002, Alex Cvetkov --> Georgy Plechanov:

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

 AC> А мне чтото подсказывает что O(n^2) Аналогичная одномерная задача
 AC> решаеться, насколко мне известно, за линейное время.
    Ты имеешь ввиду задачу нахождения непрерывной подпоследовательности с
    максимальной суммой за линейное время? Очень хотелось бы посмотреть
    алгоритм, т.к. на четвертьфинале ACM в этом году в Челябинске предлагали
    решение за O(N*logN) (очевидное за O(N^2) не проходило по времени).

                Всего хорошего. Alexey.
... А что подyмал кpолик, никто не yзнал,
--- потомy что кpолик был очень воспитанный.
 * Origin: Можно ли напиться из-за одного файла? Да. 0000FFA5.SU2 (2:5012/2.89)