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
include<bits/stdc++.h>
define N 100002
using namespace std;
int n,a[N],f[N],g[N],c[N],d[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
c[0]=0;
int m=0;
for(int i=1;i<=n;i++)
{
int x=lower_bound(c,c+m+1,a[i])-c-1;
f[i]=x+1;
if(x==m)
{
m++;
c[m]=a[i];
}
else c[x+1]=min(c[x+1],a[i]);
}
int dmax=0;
for(int i=1;i<=n;i++)
{
dmax=max(dmax,f[i]);
}
cout<<dmax;
return 0;
}
6 bình luận nữa