最长上升子序列

Sample Input

8
5 2 8 6 3 6 9 7

Sample Output

4
2 3 6 7

要求找出最长的上升子序列，然后输入子序列。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     ios_base::sync_with_stdio(0); cin.tie(0);
 7     int n;
 8     int a[3006],b[3006],out[3006];
 9     while(cin>>n){
10         memset( a, 0, sizeof a);
11         memset( b, 0, sizeof b);
12         memset( out, 0, sizeof out);
13 
14         for(int i=1;i<=n;i++)
15             cin >> a[i];
16         int len=0,mid=0,o1=0;
17         for(int i=n;i>=0;i--){
18             for(int j=i+1;j<=n;j++){
19                 if(a[j]>a[i]){
20                     if(b[i]<b[j]+1||(b[i]==b[j]+1&&a[out[i]]>a[j])){ 
21                         ///自顶向下进行比较
22                         b[i]=b[j]+1;
23                         out[i]=j; ///out为数组链表
24                     }
25                 }
26             }
27         }
28 
29         cout << b[0] << endl;
30         for(int i=out[0];i!=0;i=out[i]) ///回溯输出链表
31             cout << a[i] << " " ;
32         cout << endl;
33     }
34     return 0;
35 }

因为这是要输出最长上升子序列的一个最优，所以要用两个循环遍历。

如果不需要输出最优的个子序列，那么有O（nlogn）的时间复杂度的算法。

用一个栈加二分搜索，就可以的出最长上升子序列的长度。

关于各种背包问题，三角问题，最大字段和，最大子矩阵和，最长上升子序列等等都是经典的dp入门问题。接下来会进一步加深的学习dp。