最长递减子序列

yzc2002

设有一个整数序列A1, A2, ... An，求这个序列中最长的递减子序列的长度M， 以及该序列可以划分成这种子序列的个数N
如序列：
300 250 252 275 200 138 245
折分成的子序列分别为
300 275 200 138
252 245
250
其中最长序列为：
300 275 200 138
所以M=4， N=3

yzc2002

我得到的结果是扫描一遍序列，可以得到最长子序列，要拆分所有的子序列，最差的情况下（序列递增）要拆n次，所以是个O(n*n)的

win_hate

原帖由 yzc2002 于 2006-5-9 13:55 发表
设有一个整数序列A1, A2, ... An，求这个序列中最长的递减子序列的长度M， 以及该序列可以划分成这种子序列的个数N
如序列：
300 250 252 275 200 138 245
折分成的子序列分别为
300 275 200 138
252 245
2 ...

没看懂题目。 300 250 为什么不算递减的？ 300 自己作为一个序列呢？

yzc2002

要求得到的递减子序列是最长的
举的例子不是很好,因为有很多个相同长度的递减子序列,长度都为4
再看序列
300 250 275 252 200 138 245
这个的最长子序列是
300 275 252 200 138
长度为5

[ 本帖最后由 yzc2002 于 2006-5-10 09:07 编辑 ]

tyc611

递归实现吧
给一个例子，我只计算了最长子序列的长度

1. 
   
2. #include <iostream>
   
3. using namespace std;
   
4. 
   
5. int MaxSubseq_Recur(int nums[], int count, int max);
   
6. 
   
7. int main(){
   
8.         int nums[]={300, 250, 275, 252, 200, 138, 245};
   
9.         int count=sizeof(nums)/sizeof(int);
   
10.        
    
11.         cout<<"The result of sequence {";
    
12.         for (int i=0; i<count-1; ++i)
    
13.                 cout<<nums[i]<<',';
    
14.         cout<<nums[count-1]<<"} is "<<MaxSubseq_Recur(nums, count, 350)<<endl;
    
15.        
    
16.         return 0;
    
17. }
    
18.        
    
19. int MaxSubseq_Recur(int nums[], int count, int max) {
    
20.         //在序列（nums[], count)中寻找比最长子序列，其中序列中的数应比max都小
    
21.         int tmp1, tmp2;
    
22. 
    
23.         if(count==1)
    
24.                 return nums[0]<max?1:0;
    
25.         else {
    
26.                 if(nums[0]<max) { //nums[0]可选
    
27.                         tmp1=MaxSubseq_Recur(nums+1, count-1, nums[0])+1;        //选
    
28.                         tmp2=MaxSubseq_Recur(nums+1, count-1, max);                        //不选
    
29.                         return tmp1>tmp2?tmp1:tmp2;
    
30.                 }
    
31.                 else
    
32.                         return MaxSubseq_Recur(nums+1, count-1, max);
    
33.         }
    
34. }       
    

复制代码

望大家多多指教！

[ 本帖最后由 tyc611 于 2006-5-10 10:22 编辑 ]

tyc611

还有，LZ的第二需求理解不了

yzc2002

tyc611的算法是O(2^n)的，当串的长度增大时，速度会变得很慢
如取32个数的递减序列
100, 99, 98, ..., 69
试验一下就可以看出
最小个数N是指一个串能最少分割成递减序列的个数

win_hate

以 300 250 252 275 200 138 245 为例，300 起点的最长递减子串可以归结为 比 300 小的元素起点的最长递减子串

于是有模式 f (300) = max {f(250), f(252) ....} + 1

这个跟 FB 序列有点类似，倒过来做会比较方便

300  250  252  275  200  138  245
                                          1
                                    1
                            2
                     3                           
               3
        3
4

其中每一步可以记下当前最大串数量，若要输出最大串，则可以记录转向标记，比如 200 的  next 为 138， 275 的 next 为 200,  300 的 next 为 250, 252, 257 (想法而已，大概可以实现)。

每一步都要搜索其后较小的数，若数据量比较大，可以采用辅助结构，如二叉树之类的。

[ 本帖最后由 win_hate 于 2006-5-10 14:43 编辑 ]

win_hate

再来一个例子

5 100 99 4 32 1
3  4   3   2 2  1
1  2   2   1 1  1

最长串长度为 4，有2个。

第二行是长度，第三行是数量

[ 本帖最后由 win_hate 于 2006-5-10 14:59 编辑 ]

win_hate

前面给出的算法不好，没必要从尾开始搜索。改 ``以 xx 起点的串‘’ 为 ``以 xx 结尾的串'' 则可以从头开始处理。

例子

300 250 275 252 200 128 245

1     2    2     3     4     5    4