Q：例如：有一个序列，例如 9 8 2 1 7 5 3 4 3 2 1.

     求出最长的递减子序列。如本例的结果就是：9 8 7 5 4 3 2 1。

分析：

        可采用动态规划的思想进行解答，时间复杂度为O(n^2).

       设原数组为a[1....n]。另设一数组d[1....n],其中d[i]表示从第i个元素开始（一定包含第i个元素），到整个数组末尾的子序列 a[i...n]中的最长递减子序列的长度。

       则本问题就是要在求出d[1]的同时，恢复出最优解。

   下面给出递推式：

d[i]的值分两种情况：

1、当i=n时，d[i]=1。即最后一个元素的序列的最大递减子序列中只有它自己。

2、当i<n时，d[i]=max{d[k]| i<k<=n 且a[i]>a[k]} +1。解释意思为，包含第i个元素的序列a[i...n]的最大子序列依赖于i后面所有的序列中比a[i]小（满足递减

特性），且最大的d[k]（满足最 优特性）值再加1（加上a[i]元素）。在给d[i]赋值的时候只需记录p[i]=k,既可以作为parent属性恢复出解。

具体实现的话，开两个数组d[n],p[n]，外层循环从后往前选取i，内层循环从i往后寻找最优的k,双循环遍历即可求出所有的d[i]。然后 再进行一次O（n)操作，找出最大的d[max]。恢复解的话，可以从p[max]开始，依次恢复出各个解。

#include 
     
       2  3 void longest_decrease_sub(int *a, int size) 4 { 5      6     int *d=new int[size]; //分配内存空间     7     int *p=new int[size];  //分配内存空间 8      9     d[size-1]=1;10     11     for(int i=size-1;i>=0;i--)12     { 14         int max=0;   16         int index=0;17         18         for(int j=i;j
      
       a[j] && max 
       
        max)61         {62             63             max=d[i];64             65             max_index=i;66             67         }       69     }70     71     //从最大子序列的下标开始 输出子序列    72     cout<<"\n最长递减子序列的长度为："<
        
         <<",最长子序列为："<
        
       
      
     

 

 

 

另外一个代码版本：

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5  6 int main() 7 { 8     int n,m; 9     cin>>n;10     while (n--) {11         cin>>m;12         vector
       
        b(m);13         vector
        
         f(m);14         for(int i=0;i
         
          >b[i];17             f[i]=1;18         }19         for(int i=1;i
          
           =b[i]&&f[j]+1>f[i])23 f[i]=f[j]+1;24 }25 int max=1;26 for(int i=0;i
           
            max)29 max=f[i];30 }31 cout<
            
             <