cadane.pas

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ố).