2 qq 40229278 qq_40229278 于 2018.04.16 22:18 提问

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

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

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

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

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

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

2个回答

caozhy
caozhy   Ds   Rxr 2018.04.17 00: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]<<" ";  
}  
Never__Give_Up_
Never__Give_Up_   2018.04.19 10: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;
}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
求一个数组的最长的单调自增子序列(C代码实现)
题目: 给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱) 例如:给定一个长度为8的数组A{1,3,5,2,4,6,7,8},则其最长的单调递增子序列为{1,2,4,6,7,8},长度为6。 输入:数组,数组长度 输出:输出该数组最长递增子序列的长度 解题思想: 1、先对原始数组进行排序,原数组为{1,3,5,2,4,6,7
C++ 最长递增子序列问题
最长递增子序列问题:在一列数中寻找一些数,这些数满足:任意两个数a[i]和a[j],若i动态规划求一序列的最长子序列的长度,那么将问题变为在序列中求以a[k]为终点的最长上升子序列的长度aLen[k],状态转移方程为: aLen[0] = 1 aLen[k] = MAX{aLen[i] ,0 <= i < k且a[i] < a[k]} + 1 因为在a[k]左边结尾小于a[k]的序列的长度的最
最长单调递增子序列的三种解法
动规基础:最长递增子序列的三种解法。附详解和代码。第一种:转化成LCS问题求解O(n*n)。第二种:设d[i]为以第i个元素结尾的最长递增子序列的长度O(n*n)。第三种:二分查找优化O(nlogn)。
单调递增最长子序列 (动态规划经典题)
单调递增最长子序列 时间限制:3000 ms  |  内存限制:65535 KB 难度:4 描述求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入第一行一个整数0 随后的n行,每行有一个字符串,该字符串的长度不会超过10000 输出输出字符串的最长递增子序列的长度 样例输入 3 aaa ababc abklm
nyist oj 17 单调递增最长子序列 (动态规划经典题)
单调递增最长子序列 时间限制:3000 ms  |  内存限制:65535 KB 难度:4 描述求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入第一行一个整数0 随后的n行,每行有一个字符串,该字符串的长度不会超过10000 输出输出字符串的最长递增子序列的长度 样例输入 3 aaa ababc abklm
NYOJ - 单调递增最长子序列(经典dp)
单调递增最长子序列 时间限制:3000 ms  |           内存限制:65535 KB 难度:4 描述 求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入第一行一个整数0 随后的n行,每行有一个字符串,该字符串的长度不会超过10000输出输出字符串的最长递增子序列的长度样例输入 3 aaa ababc abklmnc
最长递增子序列的三种算法
转载自:http://qiemengdao.iteye.com/blog/1660229 最长递增子序列   问题 给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)。例如:给定一个长度为6的数组A{5, 6, 7, 1, 2, 8},则其最长的单调递增子序列为{5,6,7,8},长度为4. 解法1:最长公共子序列法 这个问题
求单调递增最长子序列 动态规划法(DP)
***单调递增最长子序列***** 描述**求一个字符串的最长递增子序列的长度如:dabdbf最长递增子序列就是abdf,长度为4**输入**第一行一个整数0随后的n行,每行有一个字符串,该字符串的长度不会超过10000**输出**输出字符串的最长递增子序列的长度 /////////////////////////////////////////////// **基本思想** 动态规划算法
动态规划算法之最长递增子序列问题
一、问题描述 在数字序列A中,按下标递增的顺序选出一个子序列B,如果选出的子序列B是严格递增的,则该子序列B称为原数字序列A的递增子序列。最长递增子序列问题就是找到原数字序列A中最长的递增子序列。例如数字序列5,2,8,6,3,6,9,7的一个最长递增子序列为2,3,6,9。 二、问题分析 动态规划函数为 L(i) = 1,                         i = 1或者不
最长单调递增子序列 o(n^2),o(nlogn)
最长递增子序列 时间复杂度为o(n^2): #include #include #include #include #include using namespace std; int a[100]= {0}; int dp[100]= {0}; int main() { int i,j,n,m; scanf("%d",&m); while(m--) {