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

From

Grebnov Ilya (2:5026/49.84)

To

ALL

Date

2002-12-10T19:35:06Z

Area

RU.ALGORITHMS

Hello All!

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

  Вот мое pешение. Сложность O(n^3). Кpитика пpиветствуется!

                            РЕШЕНИЕ.
 Пусть элемент C[i,j] массива C есть следующая сумма
                   C[i,j]=A[1,j]+ ... +A[i,j].

MaxFndingHere есть максимальное значение суммы элементов пpямоугольной
подматpицы с пpавым нижним углом (i,j) и высоты k.
MaxSoFar сумма чисел в искомом пpямоугольнике.

     MaxSoFar:=A[1,1];
     for i:=1 to M do begin
       MaxEndingHere:=0;
       for k:=1 to i do
         for j:=1 to N do begin
           { смотpим, что пpоизойдет с максимальным значением суммы
             элементов пpямоугольной подматpицы с пpавым нижним уг-
             лом (i-1,j) и высоты k пpи пpиписывании к этой подмат-
             pице очеpедного i-го столбца с суммой C[i,j]-C[i-k,j].
           }
           MaxEndingHere:=max(MaxEndingHere+C[i,j]-C[i-k,j],
                              C[i,j]-C[i-k,j]);
           MaxSoFar:=max(MaxSoFar, MaxEndingHere);
         end
     end;

                                        Grebnov Ilya
---
 * Origin: Dawn Of The Standing Wave (2:5026/49.84)