Bài toán
Cho một mảng hai chiều NxN, tìm hình chữ nhật mà tổng các phần tử trong đó là lớn nhất.
Độ phức tạp
O(n^3)
Code này của Nguyễn Tiến Trung Kiên
{$mode objfpc}
{$coperators on}
procedure maximize(var a : integer; b : integer);
begin
if a<b then a := b;
end;
procedure minimize(var a : integer; b : integer);
begin
if a>b then a := b;
end;
type oo = 0..123;
var n : integer;
a : array [oo, oo] of integer;
s : array [oo, oo, oo] of integer;
function maximumSum(const a : array of integer) : integer;
var lowest : integer = 0;
current : integer = 0;
i : integer;
begin
result := low(result);
for i := low(a) to high(a) do
begin
current += a[i];
maximize(result, current - lowest);
minimize(lowest, current);
end;
// writeln('maximumSum = ', result);
end;
var i, j, k : integer;
answer : integer; //
begin
readln(n);
answer := low(answer);
for i := 1 to n do
for j := 1 to n do
read(a[i][j]);
for i := 1 to n do
for j := i to n do
for k := 1 to n do
s[i][j][k] := s[i][j-1][k] + a[j][k];
for i := 1 to n do
for j := i to n do
maximize(answer, maximumSum(s[i][j][1..n]));
writeln(answer);
end.
Nhận xét
s[i][j] là mảng lưu tổng của a[i..j], tức là s[i][j][k] = a[i..j][k].
hàm maximumSum trả về tổng các phần tử liên tiếp lớn nhất trong mảng a (ở tham số).