Решение задачи 12.
Комбинируем идеи пунктов a) и c) задачи 16 (глава "Сортировки и последовательности"). Пусть элемент C[i,j] массива C есть следующая сумма
C[i,j]=A[1,j]+ ... +A[i,j].
Переменная MaxSoFar имеет то же самое назначение, что и раньше,MaxFndingHere есть максимальное значение суммы элементов прямоугольной подматрицы с правым нижним углом (i,j) и высоты k.
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
{смотрим, что произойдет с максимальным значением суммы элементов прямоугольной подматрицы с правым нижним углом (i-1,j) и высоты k при приписывании к этой подматрице очередного 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;
|
