POJ 1631 Bridging signals ( Easy LIS )

1631 -- Bridging signals
tozangezan.hatenablog.com
tozangezanさんのブログでセグメント木の問題をたくさんもらいました、ありがとうございます。でもこれだけは。。。LISだけじゃないの？と自分を疑いながらとりあえずか書いてみました。ACしました。まぁ、本気でやるならセグメント木をやってもいいけど。。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e4 + 4;
const int INF = 0x3f3f3f3f;

int n;
int a[ MAXN ];

int v[ MAXN ];
void solve(){
    memset( v, INF, sizeof(v) );
    for(int i = 0; i < n; ++i){
        int idx = lower_bound( v, v + n, a[ i ] ) - v;
        v[ idx ] = a[ i ];
    }
    for(int i = n - 1; i >= 0; --i)
        if( v[ i ] < INF ){
            printf("%d\n", i + 1);
            return;
        }
}

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[ i ]);
        solve();
    }
    return 0;
}