생각을 더 꼼꼼히!!

14003_가장 긴 증가하는 부분 수열 5

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int n;
int map[1000002];
int p1[1000002];
int t[1000002];
stack<int> st;
int main() {
    cin>>n;
    for(int i=1; i<=n; i++)
        scanf("%d",&map[i]);
    t[1]=map[1];
    p1[1]=1;
    int pIndex=1;
    for(int i=2; i<=n; i++) {
        if(map[i]>t[pIndex]) {
            pIndex++;
            p1[i]=pIndex;
            t[pIndex]=map[i];
        } else {
            int lowIndex = lower_bound(t+1, t+pIndex,  map[i])-t;
            p1[i]=lowIndex;
            t[lowIndex]=map[i];
        }
    }
    int len = pIndex;
    for(int i=n; i>=1; i--){
        if(p1[i]==len) {
            st.push(map[i]);
            len--;
        }
    }
    cout<<pIndex<<endl;
    while (!st.empty()) {
        printf("%d ",st.top());
        st.pop();
    }
    cout<<endl;
}