Cho một dãy số nguyên ~a[1], a[2], \dots, a[n]~. Ta muốn tìm một dãy con của dãy này sao cho:

• Các phần tử được lấy theo đúng thứ tự xuất hiện trong dãy ban đầu (chỉ được bỏ qua phần tử, không được đổi chỗ).
• Dãy con đó tăng nghiêm ngặt, tức là mỗi phần tử đứng sau phải lớn hơn phần tử đứng trước.

Dãy con thỏa điều kiện và có độ dài lớn nhất gọi là Dãy con tăng dài nhất (LIS – Longest Increasing Subsequence).

Ví dụ:

$$ a = [10, 9, 2, 5, 3, 7, 101, 18] $$

Một LIS điển hình là:

$$ [2, 3, 7, 101] $$

với độ dài ~4~.

Yêu cầu

Cho dãy số nguyên ~a[1], a[2], \dots, a[n]~.
Hãy tìm độ dài của dãy con tăng nghiêm ngặt dài nhất.

Dữ liệu

• Dòng đầu tiên: số nguyên dương ~n~ (~1 ≤ n ≤ 1000~).
• Dòng thứ hai: ~n~ số nguyên ~a[i]~ (có thể âm hoặc dương).

Kết quả

• In ra một số nguyên duy nhất – độ dài LIS.

Ví dụ

Ví dụ 1

Input

8
10 9 2 5 3 7 101 18

Output

4

Ví dụ 2

Input

6
5 5 5 5 5 5

Output

1

Giải thích

Ví dụ 1

Nhìn vào dãy:

$$ 10, 9, 2, 5, 3, 7, 101, 18 $$

Một dãy con tăng dài nhất là:

$$ 2, 3, 7, 101 $$

nên độ dài bằng ~4~.

Ví dụ 2

Tất cả phần tử đều bằng nhau → không thể tạo dãy tăng nghiêm ngặt → LIS = 1.

Gợi ý thuật toán Quy hoạch động (O(n²))

Định nghĩa:

• ~f[i]~ = độ dài LIS kết thúc tại vị trí ~i~.

Khởi tạo:

• ~f[i] = 1~ với mọi ~i~.

Chuyển:

• Với mọi ~j < i~, nếu ~a[j] < a[i]~ thì:

$$ f[i] = \max(f[i], f[j] + 1) $$

Đáp án cuối cùng:

$$ \max_{1 \le i \le n} f[i] $$

Chấm điểm