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.

Download