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

Email 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 *