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

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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 *