最大不下降子序列

F[i]表示从i开始最大不下降子序列长度。
　　　　1 i=length
F[i]=　 1 i<j<=lengt && ai > aj
mx{F[j]}+1 i<j<=length && ai <= aj
倒着来，长度递增遍历。
 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 
 5 
 6 void longest_nodecreaseing_subsequence(vector<int> &v, vector<int> &printout, vector<int> &F)
 7 {    
 8     for(int i=v.size()-1; i>=0; --i)
 9     {
10         if(i == v.size()-1)
11         {
12             F[i]=1; printout[i]=i;
13         }
14         else
15         {
16             /*max记录一趟遍历中最长长度, index记录最长子序列的后继*/
17             int max(-1), index(-1);
18             for(int j=i+1; j<v.size(); ++j)
19             {
20                 if(v[j] < v[i])
21                 {
22                     if(max < 1)
23                     {
24                         max=1; index=i;
25                     }
26                 }
27                 else
28                 {
29                     if(F[j]+1 > max)
30                     {
31                         max=F[j]+1;
32                         index = j;
33                     }
34                 }
35             }
36             F[i]=max; printout[i]=index;
37         }
38     }
39 }
40 
41 void Print(vector<int> &v, vector<int> &printout, int i)
42 {
43 
44     if(printout[i] == i)
45         cout<<v[i]<<endl;
46     else
47     {
48         cout<<v[i]<<" ";
49         Print(v, printout, printout[i]);
50     }
51 }
52 
53 int main()
54 {
55     int N;
56     while(cin>>N)
57     {
58         vector<int> v(N);
59         for(int i=0; i<N; ++i)
60             cin>>v[i];
61         /*printout[i]记录第i结点最长子序列的后继位置*/
62         vector<int> printout(N);
63         /*F(i)表示从下标i开始的最长不下降子序列长度*/
64         vector<int> F(N);
65         longest_nodecreaseing_subsequence(v, printout, F);
66         cout<<F[0]<<endl;
67         Print(v, printout, 0);
68     }
69     return 0;
70 }
71 /* 21 个 5 6 3 9 5 9 5 6 2 56 925 298 35 3 57 95 3 5 9 88 632*/