Dãy con tăng dài nhất (bản khó)
Xem PDF
Điểm:
400 (p)
Thời gian:
0.2s
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],\cdots A[N]\).
Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],\cdots A[i_k]\) thỏa mãn \(i_1<i_2< \cdots <i_k\) và \(A[i_1]<A[i_2]< \cdots <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ử.
Input
- Dòng đầu tiên chứa số nguyên dương \(N (1 \leq N \leq 30000)\)
- Dòng thứ 2 ghi \(N\) số nguyên \(A[1],A[2],\cdots ,A[N](0 \leq A[i] \leq 1000000)\).
Output
- Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.
Example
Test 1
Input
6
1 2 5 4 6 2 Output
4
Bình luận
include <bits/stdc++.h>
using namespace std;
int main(){
multiset <int> mulse;
int n, a, m;
cin>>n;
for(int i = 1; i <= n; i++) {
cin>>a;
mulse.insert(a);
auto m=mulse.lower_bound(a);
m++;
if (m!=mulse.end())
mulse.erase(m);
}
cout<<mulse.size();
return 0;
}
7 bình luận nữa