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

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条)

报告相同问题?

悬赏问题

  • ¥15 kafka topic 所有分副本数修改
  • ¥15 小程序中fit格式等运动数据文件怎样实现可视化?(包含心率信息))
  • ¥15 如何利用mmdetection3d中的get_flops.py文件计算fcos3d方法的flops?
  • ¥40 串口调试助手打开串口后,keil5的代码就停止了
  • ¥15 电脑最近经常蓝屏,求大家看看哪的问题
  • ¥60 高价有偿求java辅导。工程量较大,价格你定,联系确定辅导后将采纳你的答案。希望能给出完整详细代码,并能解释回答我关于代码的疑问疑问,代码要求如下,联系我会发文档
  • ¥50 C++五子棋AI程序编写
  • ¥30 求安卓设备利用一个typeC接口,同时实现向pc一边投屏一边上传数据的解决方案。
  • ¥15 SQL Server analysis services 服务安装失败
  • ¥15 基于面向对象的图书馆借阅管理系统