Chris_kxt 2018-04-16 14:18 采纳率: 100%
浏览 2855
已采纳

C++语言编程 单调递增最长子序列

7-1 单调递增最长子序列
设计一个O(n2)时间的算法,找出由n个数组成的序列的最长单调递增子序列。
输入格式:

输入有两行: 第一行:n,代表要输入的数列的个数 第二行:n个数,数字之间用空格格开
输出格式:

最长单调递增子序列的长度
输入样例:

在这里给出一组输入。例如:
5
1 3 5 2 9
输出样例:

在这里给出相应的输出。例如:
4

  • 写回答

2条回答 默认 最新

  • threenewbee 2018-04-16 16:08
    关注

    参考:https://blog.csdn.net/lucienduan/article/details/24397949

     /************************************************************************/  
    /* 算法导论15.4-5 
     * 找出n个数的序列中最长的单调递增子序列 
     * 利用动态规划思想,时间复杂度为O(n^2)*/  
    /************************************************************************/  
    #include<iostream>  
    using namespace std;  
    void printSequence(int *b,int* nums,int last);  
    int main()  
    {  
        int n=8;  
        int nums[9]={0,1,7,8,9,2,3,4,5};  
        //b存储当前元素所在递增子序列中当前元素的前一个元素序号  
        //c存储以当前元素结尾的递增子序列长度  
        //last存储当前元素为止的序列中最长递增子序列的最后一个元素的序号  
        //maxLen存储当前最长递增子序列的长度  
        int b[9]={0},c[9]={0},last[9]={0},maxLen=0;  
        c[1]=1,last[1]=1;  
        for (int i=1;i<=n;i++)  
        {  
            for (int j=1;j<i;j++)  
            {  
                if(nums[j]<nums[i] && c[j]+1>c[i])  
                {  
                    c[i]=c[j]+1;  
                    b[i]=j;  
                    last[i]=i;  
                    maxLen=c[i];  
                }else if(c[j]>c[i]){  
                    maxLen=c[j];  
                    last[i]=last[j];  
                }  
            }  
        }  
        cout<<"原序列长度为"<<n<<",如下:"<<endl;  
        for (int i=1;i<=n;i++)  
        {  
            cout<<nums[i]<<" ";  
        }  
        cout<<endl<<"最长递增子序列长度为"<<maxLen<<",如下:"<<endl;  
        printSequence(b,nums,last[n]);  
        cout<<endl;  
        return 0;  
    }  
    
    void printSequence(int *b,int* nums,int last)  
    {  
        if(b[last]>0)  
            printSequence(b,nums,b[last]);  
        cout<<nums[last]<<" ";  
    }  
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 C#调用python代码(python带有库)
  • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面