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 = (a1, a2, …, an). 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 liu:

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

l  Dòng 2 chứa n số nguyên a1, a2, …, an (“i: |ai| ≤ 109) 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

INPUTOUTPUT
1188 99 11 22 22 33 11 66 33 44 77

 

4

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

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *