Longest Ordered Subsequence

最长上升子序列的两种算法

(1) O(n^2)

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 const int N=10010;
 5 int dp[N],a[N];//dp[i]表示0~i的最长上升子序列的长度
 6 int n;
 7 
 8 int main()
 9 {
10     int n;
11     while(~scanf("%d",&n))
12     {
13         memset(dp,0,sizeof(dp));
14         for (int i = 0; i < n; i++)
15             scanf("%d",&a[i]);
16         int Max = 1;
17         dp[0] = 1;
18         for (int i = 1; i < n; i++)
19         {
20             dp[i] = 1; //初始所有值的最长上升子序列长度
21             for (int j = 0; j < i; j++)
22             {
23                 if (a[i]> a[j] && dp[j]+1>dp[i])//用所有a[i]之前的并小于a[i]的数的上升子序列长度，更新dp[i]
24                 dp[i] = dp[j]+1;
25             }
26             if (Max < dp[i])
27                 Max = dp[i];//找出最长的上升子序列长度
28         }
29         printf("%d
",Max);
30     }
31     return 0;
32 }

View Code

1 #include <stdio.h> 2 #include <string.h> 3 const int N=10010; 4 const int INF=-1<<28; 5 int c[N],n; 6 7 int Bin_search(int key,int len) 8 { 9 int l = 1; 10 int r = len; 11 12 while(l <= r) 13 { 14 int mid = (l+r)>>1; 15 if (key > c[mid]) 16 l = mid+1; 17 else 18 r = mid-1; 19 } 20 return l; 21 } 22 int main() 23 { 24 while(~scanf("%d",&n)) 25 { 26 int a,pos = 0,len=0; 27 c[len] = INF; 28 for (int i = 0; i < n; i++) 29 { 30 scanf("%d",&a); 31 if (a > c[len]) 32 pos = ++len; 33 else 34 pos = Bin_search(a,len); 35 c[pos] = a; 36 } 37 38 printf("%d ",len); 39 } 40 return 0; 41 }

相关推荐