1 //Accepted    3540 KB    62 ms 2 //dp 最长上升子序列 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int imax_n = 400005; 8 int dp[imax_n]; 9 int d[imax_n];10 int a[imax_n];11 int n;12 int len;13 int max(int a,int b)14 {15     return a>b?a:b;16 }17 int binary_search(int k)18 {19     int l=0;20     int r=len;21     while (l<=r)22     {23         int mid=(l+r)/2;24         if (d[mid]==k) return mid;25         if (d[mid]<k) l=mid+1;26         if (d[mid]>k) r=mid-1;27     }28     return l;29 }30 void Dp()31 {32     memset(dp,0,sizeof(dp));33     memset(d,0,sizeof(d));34     len=-1;35     for (int i=0;i<n;i++)36     {37         int j=binary_search(a[i]);38         if (j>len) len++;39         dp[i]=j+1;40         d[j]=a[i];41     }42     int ans=0;43     for (int i=0;i<n;i++)44     ans=max(ans,dp[i]);45     printf("%d\n",ans);46 }47 int main()48 {49     int T;50     scanf("%d",&T);51     while (T--)52     {53         scanf("%d",&n);54         for (int i=0;i<n;i++)55         scanf("%d",&a[i]);56         Dp();57     }58     return 0;59 }