Dãy con tăng dài nhất cơ bản

Buổi 22 — DP 2D & LIS Dynamic Programming
Points
10
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho một dãy số nguyên $A$ gồm $N$ phần tử $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 (LIS) của $A$. Dãy con thu được bằng cách xóa đi một số phần tử (có thể không xóa phần tử nào) mà giữ nguyên thứ tự ban đầu.

Cấu trúc con tối ưu: $dp[i] = 1 + \max_{j < i, A_j < A_i} dp[j]$.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$. Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$.

Dữ liệu ra

Một số nguyên duy nhất là độ dài của dãy con tăng dài nhất.

Ví dụ
Input Output
6
3 1 4 1 5 9
4
5
5 4 3 2 1
1
Giới hạn

$1 \le N \le 2000$, $|A_i| \le 10^9$.

Draft saved