Sample Input

8

5 2 8 6 3 6 9 7

Sample Output

4

2 3 6 7

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

1 #include
      
        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]
       
        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。