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

From

Alex Cvetkov (2:5030/1334)

To

Georgy Plechanov

Date

2002-12-10T11:51:46Z

Area

RU.ALGORITHMS

Hello Georgy!

09 Дек 02 12:38, Georgy Plechanov писал(ла) Slava Gorbanev:

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

А мне чтото подсказывает что O(n^2) Аналогичная одномерная задача решаеться, насколко мне известно, за линейное время.

                                           Alex Cvetkov

--- Клиент морга
 * Origin: Life suxx (2:5030/1334)