BCINCSEQ spoj PTIT – Đoạn tăng

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCINCSEQ/

1. Đề bài BCINCSEQ spoj PTIT

Cho dãy số nguyên A = (a₁, a₂, …, a_n). Hãy tìm một đoạn dài nhất gồm các phần tử liên tiếp trong dãy A có thứ tự không giảm

Quy ước: Đoạn chỉ gồm đúng 1 phần tử trong A cũng được coi là có thứ tự không giảm

Dữ liệu:

l  Dòng 1 chứa số nguyên dương n ≤ 10⁵

l  Dòng 2 chứa n số nguyên a₁, a₂, …, a_n (“i: |a_i| ≤ 10⁹) cách nhau ít nhất một dấu cách

Kết quả:một số nguyên duy nhất là số phần tử trong đoạn tìm được

Ví dụ

2. Hướng dẫn BCINCSEQ spoj PTIT

– Gọi F[i] là độ dài xâu con liên tiếp dài nhất kết thúc tại phần tử có giá trị là A[i].

– Nếu a[i]>=A[i-1] thì F[i]:=F[i-1]+1

– Ngược lại F[i]:=1

Kết quả bài toán là F[n].

Khởi tạo F[0]=0; A[0]=dương vô cực.

3. code tham khảo BCINCSEQ spoj PTIT

CONST   FI='';
        nmax=100000;
type    data=longint;
var
        f:text;
        a:array[0..nmax+1] of data;
        n,i,j,max:data;
        C:array[0..nmax+1] of data;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        readln(f,n);
        for i:=1 to n do
                read(f,a[i]);
        a[0]:=high(data);
        close(f);
end;

begin
        docfile;
        max:=0;
        for i:=1 to n do
                if a[i-1]<=a[i] then
                        C[i]:=C[i-1]+1
                else
                        C[i]:=1;
        for i:=1 to n do
                if c[i]>max then
                        max:=c[i];
        writeln(max);
end.