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

From

Ilia Kantor (2:5020/175.2)

To

Georgy Plechanov

Date

2002-12-09T15:03:59Z

Area

RU.ALGORITHMS

From: "Ilia Kantor" <ilia@manual.ru>

Mon Dec 09 2002 12:38, Georgy Plechanov wrote to Slava Gorbanev:

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

Перебираем все прямоугольники, состоящие из соседних строк

for(i=0;i<100;i++)
  for(j=i;j<100;j++)
    { обработать прямоугольник из строк i..j }

В каждом таком прямоугольнике будем искать максимальную подматрицу, включающую
в себя отрезки строк i..j, т.е полностью заполняющую прямоугольник сверху
донизу.

 * * * * * * *
 * [* * * *] *  i
 * [* * * *] *
 * [* * * *] *  j
 * * * * * * *
 
Такую подматрицу можно найти простым сканирующим алгоритмом, аналогично
одномерному случаю.

Итого, алгоритм имеет сложность n^3 = 10^6 операций. Быстрее можно, но не так,
чтобы намного. Квадратичный алгоритм мне неизвестен, да и вряд ли есть.

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)