Dãy con tăng dài nhất (bản dễ)
Xem PDF
Điểm:
1400 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
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[i_1],... A[i_k]\) thỏa mãn
\(i_1 < i_2 < ... < i_k\) và \(A[i_1] < A[i_2] < .. < A[i_k]\).
Yêu cầu:
- 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ử.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 ≤ N ≤ 1000\))
- Dòng thứ 2 ghi N số nguyên \(A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 1000000)\).
Kết quả
- Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.
Test 1
Input
6
1 2 5 4 6 2Output
4Nguồn: vn.spoj
Bình luận
sử dụng quy hoạch động
code đã AC
include<bits/stdc++.h>
using namespace std;
int n,a[1000005],t;
int main(){
cin>>n;
vector<int>l(n,1);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++)
for(int j=0;j<i;j++){ if(a[i]>a[j])
l[i]=max(l[i],l[j]+1);
}
cout<<*max_element(l.begin(),l.end())<<'\n';
}
6 bình luận nữa