#include<stdio.h>
int a[] , temp[] ;
int n , top ; int binary_search (int x) {
int fir = ;
int last = top ;
int mid ;
while (fir <= last ) {
mid = (fir + last) / ;
if ( x <= temp[mid] ) {
last = mid - ;
}
else {
if (x <= temp[mid + ] )
return mid + ;
else
fir = mid + ;
}
}
} int main () {
// freopen ("a.txt" ,"r" , stdin) ;
while ( scanf ("%d" , &n ) != EOF ) {
for (int i = ; i < n ; i++ ) {
scanf ("%d" , &a[i]) ;
} top = ;//目前最长不下降子序列的长度
temp[top] = a[] ;////temp[i]为长度为i的上升子序列末尾元素的最小值
for (int i = ; i < n ; i++ ) {
if ( a[i] >= temp[top] ) {
temp[++top] = a[i] ;
}
else {
if ( a[i] < temp[] ) {
temp[] = a[i] ;
}
else {
temp[binary_search(a[i])] = a[i] ;
}
}
}
printf ("%d\n" , top + ) ;
}
return ;
}
用二分查找法
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
const int inf = 0x3f3f3f3f ;
std::vector <int> g[ + ] ;
int a[] ;
int dp[] ;
int n ; int dfs (int id , int dep )
{
if (dp[id] != ) return dp[id] ;
if (id == n - ) return dp[id] ;
bool flag = ;
for (int i = id + ; i < n ; i ++) {
if (a[i] > a[id]) {
g[dep].push_back (dfs ( i , dep + ) ) ;
flag = ;
}
}
if (flag) {
int t = max_element (g[dep].begin () , g[dep].end () ) - g[dep].begin () ;
dp[id] += g[dep][t] ;
g[dep].clear () ;
}
return dp[id] ;
} int main ()
{
// freopen ("a.txt" , "r" , stdin ) ;
while ( ~scanf ("%d" , &n) ) {
memset (dp , , sizeof(dp)) ;
for (int i = ; i < n ; i ++) scanf ("%d" , &a[i]) ;
for (int i = ; i < n ; i ++) dp[i] = ;
for (int i = n - ; i >= ; i --) { dfs (i , ) ; }
int len = -inf ;
for (int i = ; i < n ; i ++) len = std::max (len , dp[i]) ;
printf ("%d\n" , len ) ;
}
return ;
}
记忆化搜索