QTSEQ - Dãy số QT
Tác giả: ladpro98
Ngôn ngữ: Pascal
program QTSEQ;
uses math;
const fi='';
maxn=trunc(1e6)+6;
oo=2*trunc(1e9);
var a,cmin,cmax:array[0..maxn] of longint;
maxPs,minPs,ps:array[0..maxn] of int64;
n,i:longint;
S,res,cnt:int64;
begin
readln(n);
maxPs[0]:=-oo;minPs[0]:=oo;
for i:=1 to n do begin
read(a[i]);
ps[i] := ps[i-1] + a[i];
maxPs[i] := maxPs[i-1]; cmax[i] := cmax[i-1];
minPs[i] := minPs[i-1]; cmin[i] := cmin[i-1];
if (minPs[i]=ps[i]) then inc(cmin[i]);
if (maxPs[i]=ps[i]) then inc(cmax[i]);
if (maxPs[i]<ps[i]) then begin
maxPs[i] := ps[i];
cmax[i] := 1;
end;
if (minPs[i]>ps[i]) then begin
minPs[i] := ps[i];
cmin[i] := 1;
end;
end;
for i:=n downto 2 do begin
inc(S,a[i]);
if (res=abs(S-minPs[i-1])) then inc(cnt,cmin[i-1]);
if ((res=abs(S-maxPs[i-1])) and (maxPs[i-1]<>minPs[i-1])) then inc(cnt,cmax[i-1]);
if (res<abs(S-minPs[i-1])) then begin
res := abs(S-minPs[i-1]);
cnt := cmin[i-1];
end;
if (res<abs(S-maxPs[i-1])) then begin
res := abs(S-maxPs[i-1]);
cnt := cmax[i-1];
end;
end;
write(res, #32 , cnt);
end.