Dãy Con Tăng Dài Nhất
Đề bài
Mô tả
Cho mảng gồm số nguyên. Tìm độ dài dãy con tăng ngặt dài nhất (Longest Increasing Subsequence — LIS). Dãy con thu được bằng cách xóa một số phần tử mà không thay đổi thứ tự, và mỗi phần tử phải lớn hơn phần tử trước đó.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên : kích thước mảng.
Dòng thứ hai chứa số nguyên : các phần tử của mảng.
Dữ liệu ra
In ra độ dài dãy con tăng ngặt dài nhất.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 10 1 1 1 1 1 1 1 1 1 1 |
1 | Tất cả phần tử bằng nhau, LIS có độ dài |
| 10 1 2 3 4 5 6 7 8 9 10 |
10 | Mảng đã tăng ngặt, LIS là toàn bộ mảng |
Bình luận
include <iostream>
include <algorithm>
include <vector>
using namespace std; int main() { int n; cin >> n; vector <int> a (n); for (int i=0; i<n; i++) cin >> a[i]; vector <int> L(n,1); for (int i=0; i<n; i++){ for (int j=0; j<i; j++){ if (a[j]<a[i]){ L[i] = max(L[i], L[j]+1); } } } cout << *max_element(L.begin(), L.end()) << "\n"; return 0; }