Dãy con giảm dài nhất

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

1. Đề bài Dãy con giảm dài nhất

Cho một dãy gồm N số nguyên (1 ≤ N ≤ 30000). Hãy tìm dãy con giảm dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint.

Input

  • Dòng đầu tiên gồm số nguyên N.
  • Dòng thứ hai gồm N số mô tả dãy.

Output

Gồm một số nguyên duy nhất là đáp số của bài toán

Example

Input:
5
3 1 2 4 0

Output:
3

2. Hướng dẫn dãy con giảm dài nhất:

Bài này như bài LIS, các bạn có thể tham khảo https://kienthuc24h.com/lis-day-con-tang-dai-nhat-ban-kho/

3. code tham khảo dãy con giảm dài nhất

 

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 *