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

From

Alexey Burdin (2:5012/32.768)

To

All

Date

2002-12-07T23:42:57Z

Area

RU.ALGORITHMS

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

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

    На ум (?) сразу приходит полный перебор: 1<=x1,y1<=100 , x1<=x2<=100,
    y1<=y2<=100, s=sum a[y,x] x1<=x<=x2, y1<=y<=y2.
    Для матрицы 100х100 считал на Celeron 466 аж 15 минут :)
    Хотелось бы что-нибудь более оптимальное, но влезающее в досовые 400к :),
    желательно чтобы работало на "раз-два-три".

                Всего хорошего. Alexey.
... А что подyмал кpолик, никто не yзнал,
--- потомy что кpолик был очень воспитанный.
 * Origin: I do... hope you have a clue (2:5012/32.768)