LIS 인쇄

오늘 후배가 OJ에 16급을 주는 선발 문제를 걸고 나는 물에 갔다.LIS를 프린트한 물문제를 발견하니 재미있다(^o^)/~, 기록해 주세요.(세그먼트 트리의 해답을 구하는 방법은 말하지 않겠다)
dp[i] d p [i]는 a[i] a [i]로 끝나는 LIS 길이를 나타냅니다.
g[i] g[i]는 길이가 ii인 모든 LIS에서 가장 작은 엔딩 요소를 나타냅니다.
만약에 서열의 LIS 길이가 ans a ns라고 가정하면 우리는 g[] g []를 통해 가능한 끝 요소 g[ans] g [a n s](여러 개가 있으면 서열 끝에서 가장 가까운 것을 선택할 수 있다. 그러면 앞에서 (ans - 1)(a n s - 1) 개의 요소를 찾아야 한다.
찾는 동안 요소를 찾을 때마다 ans a n s (현재 LIS의 남은 길이) 를 1로 줄입니다.만약에 a[i]a[i]원소가 합법적이라면 반드시 a[i]a[i]가 이전 원소보다 작고 dp[i]dp[i]는 현재 LIS의 남은 길이와 같다.
프로그램:

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 1e5 + 10;
const int N = 1e9;
typedef long long LL;
const int INF = 15000000 + 10;
int a[200100 + 10];
int dp[200100 + 10];
int g[200100 + 10];
int Stack[200100 + 10], top;
int main()
{
    int n;
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            g[i] = INF;
        }
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            int id = lower_bound(g + 1, g + n + 1, a[i]) - g;
            dp[i] = id;
            g[dp[i]] = min(g[dp[i]], a[i]);
            ans = max(ans, dp[i]);
        }
        printf("%d
", ans);
        top = 0; Stack[top++] = g[ans];
        int N;
        for(int i = n; i >= 1; i--) {
            if(a[i] == g[ans]) {
                N = i; break;
            }
        }
        int mark = g[ans]; ans--;
        for(int i = N - 1; i >= 1; i--) {
            if(a[i] < mark && dp[i] == ans) {
                mark = a[i]; ans--;
                Stack[top++] = a[i];
            }
        }

        for(int i = top - 1; i >= 0; i--) {
            printf("%d
", Stack[i]);
        }
    }
    return 0;
}