최대 상승 하위 시퀀스(LIS)

#include <bits/stdc++.h>  // DP
using namespace std;
#define N 40010
int dp[N];
int data[N];

int main()
{
    int T, n, ans;
    cin>>T;
    while(T--)
    {
        cin>>n;
        ans = 0;
        for(int i=0; i<n; i++)
            dp[i] = 1;
        for(int i=0; i<n; i++)
            scanf("%d", &data[i]);
        for(int i=1; i<n; i++)
        {
            for(int j=i-1; j>=0; j--)
            {
                if(data[j]<data[i] && dp[j]+1 > dp[i])
                    dp[i] = dp[j] + 1;
            }
            ans = max(ans, dp[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define N 40010
int Binary(int *a, int l, int r, int value)
{
    while(l<=r)
    {
        int mid = (l+r) / 2;
        if(a[mid] > value)
            r = mid-1;
        else
            l = mid+1;
    }
    return l;
}
int data[N];
int ans[N];
int main()
{
    int T, n;
    cin>>T;
    while(T--)
    {
        cin>>n;
        int cnt = 0;
        for(int i=0; i<n; i++)
            scanf("%d", &data[i]);
        ans[0] = data[0];
        for(int i=1; i<n; i++)
        {
            if(data[i]>ans[cnt])
            {
                ans[++cnt] = data[i];
            }
            else
            {
                int in = Binary(ans, 0, cnt, data[i]);
                ans[in] = data[i];
            }
        }
        for(int i=0; i<=cnt; i++)
            cout<<ans[i]<<" ";
        cout<<endl;
        cout<<cnt+1<<endl;
    }
    return 0;
}