cadane (2).pas
Bài toán
Tìm dãy con liên tiếp có tổng lớn nhất.
Độ phức tạp
O(n)
Code này của Nguyễn Tiến Trung Kiên
{$mode objfpc}
{$coperators on}
uses math;
var
n: integer;
a, s: array [0..1000000] of integer;
function maximize(var a: integer; b: integer): boolean;
begin
Result := a<b;
if a<b then a:=b;
end;
function minimize(var a: integer; b: integer): boolean;
begin
Result := a>b;
if a>b then a:=b;
end;
procedure solve;
var
i: integer;
Min: integer = 0;
Max: integer = Low(integer);
CountMax: int64 = 0;
CountMin: integer = 1;
begin
readln(n);
for i := 1 to n do
read(a[i]);
for i := 1 to n do
s[i] := s[i-1] + a[i];
for i := 1 to n do
begin
if maximize(Max, s[i]-Min) then
CountMax := 0;
if Max=s[i]-Min then
CountMax += CountMin;
if minimize(Min, s[i]) then
CountMin := 0;
if Min=s[i] then
CountMin += 1;
end;
writeln(Max, ' ', CountMax);
end;
var
t: integer;
begin
readln(t);
for t := 1 to t do
solve;
end.
Nhận xét
Tham khảo