LIQ spoj – Dãy con tăng dài nhất

Nguồn đề bài: http://vn.spoj.com/problems/LIQ/

1. Đề bài LIQ Dãy con tăng dài nhất

Cho một dãy số nguyên gồm N phần tử A[1], A[2], … A[N].
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i1],… A[ik] thỏa mãn
i1 < i2 < … < ik và A[i1] < A[i2] < .. < A[ik]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?

Download test và solution (C/C++, Pascal) tại đây.

Input

  • Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 1000).
  • Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10000).

Output

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Ví dụ

Input:
6
1 2 5 4 6 2

Output:
4

Giải thích test ví dụ: Dãy con dài nhất là dãy A[1] = 1 < A[2] = 2 < A[4] = 4 < A[5] = 6, độ dài dãy này là 4.

Gợi ý: Sử dụng phương pháp Quy Hoạch Động. F[i]: Độ dài dãy con đơn điệu tăng dài nhất mà phần tử cuối cùng là số A[i] này.

2. Hướng dẫn LIQ SPOJ Dãy con tăng dài nhất

– Gọi F[i] là độ dài dãy con tăng dần dài nhất kết thúc tại i

– khởi tạo F[i]=1; (với i=1..n)

– F[i]=max(F[i],F[j]+1) (A[i]>A[j] ; i=1..n, j=1..i-1).

– nghiệm bài toán Max(F[i]) (i=1..n)

3. Code tham khảo LIQ SPOJ Dãy con tăng dài nhất

a. Code Pascal

b. code c++

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 *