Chris_kxt
2018-04-16 14:18
采纳率: 71.4%
浏览 2.6k

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]<<" ";  
    }  
    
    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • Joel__Li 2018-04-19 02:56
     #include <stdio.h>
    
    #define MAX_N 1000
    
    int dp[MAX_N], a[MAX_N];
    int n;
    
    void input()
    {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
    }
    
    int max_(int a, int b)
    {
        return a > b ? a : b;
    }
    
    void slove()
    {
        //注意要res保存结果
        int res = 0;
        for(int i = 0; i < n; ++i)
           {
    
            for(int j = 0; j < i; ++j)
                if(a[j] < a[i])
                    dp[i] = max_(dp[i], dp[j] + 1);
    
            res = max_(dp[i], res);
           }
        printf("%d\n", res + 1);
    
    }
    
    int main()
    {
        input();
        slove();
        return 0;
    }
    
    
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题