方法一：时间复杂度（n^2)
我们依次遍历整个序列，每一次求出从第一个数到当前这个数的最长上升子序列，直至遍历到最 后一个数字为止，然后再取dp数组里最大的那个即为整个序列的最长上升子序列。我们用dp[i]来存放序列1-i的最长上升子序列的长度，那么 dp[i]=max(dp[j])+1,(j∈[1, i-1]); 显然dp[1]=1,我们从i=2开始遍历后面的元素即可。
View Code
1 #include<stdio.h> 2 3 int dp[1000]; 4 int a[1000]; 5 6 int main( ) 7 { 8 int i; 9 int j; 10 int n; 11 int index; 12 int ans; 13 14 i=1; 15 while( scanf("%d",&n) && n>0 ) 16 { 17 a[i] = n; 18 i++; 19 } 20 index = i - 1; 21 22 for( i = 2; i <= index; i++ ) 23 dp[i] = 0; 24 25 dp[1] = 1; 26 27 for( i = 2; i <= index; i++ ) 28 { 29 ans = dp[i]; 30 for( j = 1; j < i; j++ ) 31 { 32 if( a[i] > a[j] && dp[j] > ans ) 33 ans = dp[j]; 34 } 35 dp[i] = ans + 1; 36 } 37 38 ans = 0; 39 for( i = 1; i <= index; i++ ) 40 { 41 if( dp[i] > ans ) 42 ans = dp[i]; 43 } 44 45 printf("%d\n", ans); 46 return 0; 47 }
方法二：时间复杂度（nlog(n))
除了算法一的定义之外，增加一个数组b，b[i]用以表示长度为i最长子序列的最后一个数最小可以是多少。易证：i<j时，b[i]<b[j]。
在二分查找时，一直更新b[]内容，设此时b的总长度为k，
若1. arr[i] >= b[k], 则b[k+1] = arr[i];
若2. arr[i] < b[k], 则在b[1..k]中用二分搜索大于arr[i]的最小值，返回其位置pos，然后更新b[pos]=arr[i]。