[c++][algorithm][baekjoon]12015번 가장 긴 증가하는 부분 수열2

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

 

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

예제 입력 1 
6
10 20 10 30 20 50
예제 출력 1 
4

8
10 20 30 5 10 20 30 40
정답: 5

반례 추가 
10
4 7 10 3 1 8 7 2 5 7
Answer: 4 
7
7 9 10 8 2 3 7
Answer: 3 
10
7 10 8 10 1 2 9 9 1 10
Answer: 4 
9
2 8 3 10 5 1 5 2 3
Answer: 3 
10
10 6 5 9 10 9 3 4 7 1
Answer: 3 
10
5 8 10 3 9 1 5 8 5 6
Answer: 3 
9
3 2 8 2 10 1 2 2 3
Answer: 3 
10
3 8 10 1 5 7 9 8 9 6
Answer: 5
7
4 3 4 9 1 3 7
Answer: 3 
10
8 6 8 9 5 1 4 4 6 3
Answer: 3

 

/*[12015]가장 긴 증가하는 부분 수열2*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN ((int)1e6+10)
int N; 
int A[MAXN];
vector<int> v;
auto it = v.begin();
void InputData(){
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> A[i];
    }
}
void Solve(){
    v.push_back(A[0]);
    for(int i=1; i<N; i++){
        if(v.back() < A[i] ) v.push_back(A[i]);
        else {
            it = v.begin();
            it = lower_bound(v.begin(), v.end(), A[i]);
            *it = A[i];
        } 
    }
    cout << v.size() << endl;
}
int main(){
    InputData();
    Solve();
    return 0;
}
/*[12015]가장 긴 증가하는 부분 수열2*/