动态规划3-例9.3最长不下降子序列

港控/mmm° 2023-07-11 11:27 22阅读 0赞

例9.3最长不下降子序列  
//设有由n个不相同的整数组成的数列，记为：b(1),b(2)...b(n)且b(i)<>b(j)(i<>j),  
//若存在i1<i2<i3<...<ie且有b(i1)<b(i2)<...<b(i3),则称为长度为e的不下降序列。  
//程序要求，当原数列出之后，求出最长的不下降序列

//算法分析
    //根据动态规划的原理，由后往前进行搜索（由前往后也一样）
    //（1)对于b(n)来说，由于它是最后一个数，所以当从b(n)开始查找时，只存在长度为1的不下降序列
    //（2）若从b(n-1)开始查找，则存在下面的两种可能性：
    //a.若b(n-1)<b(n)则存在长度为2的不下降序列b(n-1),b(n)
    //b.若b(n-1)>b(n)则存在长度为1的不下降序列
    //(3)一般认为从b(i)开始，此时最长不下降序列应该按下列方法求出：
    //在b(i+1),b(i+2),...b(n)中，找出一个比b(i)大的且最长的不下降序列，作为它的后继
    //数据结构：
    //定义一个整数类型二维数组b[n][3]
    //(1)b[i][1]表示第i个数值本身
    //(2)b[i][2]表示从i位置到达n的最长不下降序列长度
    //(3)b[i][3]表示从i位置开始最长不下降序列的下一个位置，若b[i][3]=0表示后面没有连续项
    
    #include<iostream>
    using namespace std;
    
    const int MAXN=100;
    int l,k,b[MAXN][MAXN];
    
    //处理函数
    void noDescending(int n){
        for (int i = n-1; i >=1 ; i--) {
            l=0;
            k=0;
            for (int j = i+1; j <=n ; ++j) {
                if((b[j][1]>=b[i][1])&&(b[j][2]>l)){
                    l=b[j][2];
                    k=j;
                }
            }
            if(l>0){
                b[i][2]=l+1;
                b[i][3]=k;
            }
        }
    }
    
    //主函数
    int main(){
        //数据初始化
        int n;
        cin>>n;
        for (int i = 1; i <=n ; ++i) {
            cin>>b[i][1];
            b[i][2]=1;
            b[i][3]=0;
        }
    
        //调用函数
        noDescending(n);
        k=1;
    
        //输出数据
        //求最长不下降序列的起始位置
        for (int j =1; j <=n ; ++j) {
            if(b[j][2]>b[k][2]){
                k=j;
            }
        }
        cout<<b[k][2]<<endl;
        //输出最长不下降序列
        while(k!=0){
            cout<<b[k][1]<<" ";
            k=b[k][3];
        }
    }