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

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

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

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

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

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

0

2个回答

参考: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]<<" ";  
}  
0
 #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;
}

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的。是时候展现真正的技术了!
其他相关推荐
求一个数组的最长的单调自增子序列(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]的序列的长度的最
单调递增最长子序列 (动态规划经典题)
单调递增最长子序列 时间限制:3000 ms  |  内存限制:65535 KB 难度:4 描述求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入第一行一个整数0 随后的n行,每行有一个字符串,该字符串的长度不会超过10000 输出输出字符串的最长递增子序列的长度 样例输入 3 aaa ababc abklm
最长递增子序列(原创C语言)
这是我这两天才完成的原创代码,就是比较经典的求一个随机序列的最长递增子序列问题。例如: n=5 随机序列为 5 1 4 2 3,正确输出为1 2 3,即长度为3的递增子序列。里面附带实验详细说明,感兴趣的可以下来参考。 算法参考比较著名的<<算法导论>>(第二版,作者Thomas H Cormen) 如果感觉好的可以联系我qq410812645,欢迎和各位高手交流
nyist oj 17 单调递增最长子序列 (动态规划经典题)
单调递增最长子序列 时间限制:3000 ms  |  内存限制:65535 KB 难度:4 描述求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入第一行一个整数0 随后的n行,每行有一个字符串,该字符串的长度不会超过10000 输出输出字符串的最长递增子序列的长度 样例输入 3 aaa ababc abklm
求单调递增最长子序列 动态规划法(DP)
***单调递增最长子序列***** 描述**求一个字符串的最长递增子序列的长度如:dabdbf最长递增子序列就是abdf,长度为4**输入**第一行一个整数0随后的n行,每行有一个字符串,该字符串的长度不会超过10000**输出**输出字符串的最长递增子序列的长度 /////////////////////////////////////////////// **基本思想** 动态规划算法
求一整型数组的严格单调的最长连续子序列的长度
求最长连续单调子序列 package adk; import java.util.ArrayList; import java.util.Collections; import java.util.Random; public class SearchMax { public static void main(String[] args) { // 模拟有50个1到100(包
最长单调递增子序列的三种解法
动规基础:最长递增子序列的三种解法。附详解和代码。第一种:转化成LCS问题求解O(n*n)。第二种:设d[i]为以第i个元素结尾的最长递增子序列的长度O(n*n)。第三种:二分查找优化O(nlogn)。
单调递增最长子序列(LIS)&&最长公共子序列(LCS)
动态规划的经典问题,这里的讲解网上有很多非常好的,而我却还没有能力写出完整详细的理解,就附图两张吧,这两个图貌似很火,出处找不到了。 LIS LCS   动态规划的三种形式: 1.记忆递归型 2.“我为人人”递推型 3.“人人为我”递推型   递推并不是动态规划的本质,如何拆分才是核心。拆分成若干子问题. 这里看到知乎上讲解特别好的 动态规划中递推式的求解
动态规划C++实现--最长递增子序列
题目: 给定数组arr, 返回arr的最长递增子序列。举例:arr = [2, 1, 5, 3, 6, 4, 8, 9, 7], 返回的最长递增子序列为 [1, 3, 4, 8, 9]要求:如果arr长度为N,请实现时间复杂度为O(NlogN)的方法。一、 先介绍时间复杂度O(N^2)的方法,具体过程如下:1. 生成长度为N的数组dp, dp[i]表示在以arr[i]这个数结尾的情况下,arr[0...
ACM最长单调递增子序列问题(动态规划)o(n*n)C++实现
最长单调递增子序列问题(动态规划)o() // 最长单调递增子序列.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include #define N 100 using namespace std; //递归打印最长递增子序列 void print_it(char *str,i
题目17: 单调递增最长子序列
单调递增最长子序列 时间限制:3000 ms  |  内存限制:65535 KB 难度:4 描述求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入第一行一个整数0 随后的n行,每行有一个字符串,该字符串的长度不会超过10000 输出输出字符串的最长递增子序列的长度 样例输入 3 aaa ababc abklm
ACM题:单调递增最长子序列
题目地址:http://acm.nyist.net/JudgeOnline/problem.php?pid=17题目内容:描述 求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4输入第一行一个整数0<n<20,表示有n个字符串要处理 随后的n行,每行有一个字符串,该字符串的长度不会超过10000输出输出字符串的最长递增子序列的长度样例输入3 aaa a
超简单看明白如何求最长递增子序列-动态规划
最长递增子序列:给定一个长度为N的数组,找出一个最长的单调递增子序列,子序列不一定连续,但初始顺序不能乱。例如:给定一个长度为6的数组A{4, 5, 7, 1,3, 9},则其最长的单调递增子序列为{4,5,7,9},长度为4。动态规划思路:记d[i]为以任意一个A[i]为末尾元素组成的最长递增子序列的长度,找出所有位于i之前且比A[i]小的元素A[j],此时可出现两种情况:(1)若找到,例如i ...
最长递增子序列的三种算法
转载自:http://qiemengdao.iteye.com/blog/1660229 最长递增子序列   问题 给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)。例如:给定一个长度为6的数组A{5, 6, 7, 1, 2, 8},则其最长的单调递增子序列为{5,6,7,8},长度为4. 解法1:最长公共子序列法 这个问题
动态规划算法之最长递增子序列问题
一、问题描述 在数字序列A中,按下标递增的顺序选出一个子序列B,如果选出的子序列B是严格递增的,则该子序列B称为原数字序列A的递增子序列。最长递增子序列问题就是找到原数字序列A中最长的递增子序列。例如数字序列5,2,8,6,3,6,9,7的一个最长递增子序列为2,3,6,9。 二、问题分析 动态规划函数为 L(i) = 1,                         i = 1或者不
NY 单调递增最长子序列(一)
时间限制:3000 ms  |  内存限制:65535 KB 难度:4 描述 求一个字符串的最长递增子序列的长度如:dabdbf最长递增子序列就是abdf,长度为4 输入 第一行一个整数0&amp;lt;n&amp;lt;20,表示有n个字符串要处理随后的n行,每行有一个字符串,该字...
NYOJ - 单调递增最长子序列(经典dp)
单调递增最长子序列 时间限制:3000 ms  |           内存限制:65535 KB 难度:4 描述 求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入第一行一个整数0 随后的n行,每行有一个字符串,该字符串的长度不会超过10000输出输出字符串的最长递增子序列的长度样例输入 3 aaa ababc abklmnc
单调递增最长子序列 动态规划
描述求一个字符串的最长递增子序列的长度如:dabdbf最长递增子序列就是abdf,长度为4输入第一行一个整数0&amp;lt;n&amp;lt;20,表示有n个字符串要处理随后的n行,每行有一个字符串,该字符串的长度不会超过10000输出输出字符串的最长递增子序列的长度样例输入3 aaa ababc abklmncdefg样例输出1 3 7代码实现:#include&amp;lt;iostream&amp;gt;#include...
最长单调递增子序列
用动态规划方法找出由n个数a【i】(1<=i<=n)组成的序列的一个最长单调递增子序列
动态规划:单调递增子序列
给定一个长度为N的数组,找出一个最长的单调递增子序列(不一定连续,但是顺序不能乱
贪心——单调递增最长子序列
描述求一个字符串的最长递增子序列的长度如:dabdbf最长递增子序列就是abdf,长度为4 输入第一行一个整数0&amp;lt;n&amp;lt;20,表示有n个字符串要处理随后的n行,每行有一个字符串,该字符串的长度不会超过10000输出输出字符串的最长递增子序列的长度样例输入3 aaa ababc abklmncdefg样例输出1 3 7#include&amp;lt;iostream&amp;gt;#include&amp;lt;...
三种算法求一个数字序列的最长递增子序列
也有很多博客写如何实现最长递增子序列的算法,自己查阅了一些资料总结出三种实现的算法,两种是常见的处理思路,还有一种是本人自己想出来的算法,很好理解,但是效率不是特别高。 算法一: 将n个数的原序列A[n]排序后得到递增序列B[n],则把求A的最长单调递增子序列问题转化成求A、B序列的最长公共子序列(LCS)。 这个算法是算法导论书后面习题的标准答案解法了,有很多人写过实现。时间复杂度O(n^
动态规划之最长单调递增子序列(C++源码)
动态规划之最长单调递增子序列 问题: L={a1,a2,a3,…,an}既L是由n个不同的实数组成的序列,求L的最长单调递增子序列(下标可不连续)。 分析: 设辅助数组b,b[i]表示以a[i]为结尾的最长递增子序列的长度,最长递增子序列的长度,就是数组b的最大值。 代码: 最优值: #include&amp;lt;bits/stdc++.h&amp;gt; using namespace std; #defin...
最长递增子序列(动态规划实现)
题目描述: (题目来源于牛客网)对于一个数字序列,请设计一个复杂度为O(nlogn)的算法,返回该序列的最长上升子序列的长度,这里的子序列定义为这样一个序列U1,U2...,其中Ui 给定一个数字序列A及序列的长度n,请返回最长上升子序列的长度。 测试样例: [2,1,4,3,1,5,6],7 返回:4 解法:题目要求复杂度为O(nlogn),我们可以这样想,肯定是要遍历数组,这
nyoj -17 单调递增最长子序列 动归
单调递增最长子序列 时间限制:3000 ms  |  内存限制:65535 KB 难度:4 描述 求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入第一行一个整数0 随后的n行,每行有一个字符串,该字符串的长度不会超过10000输出输出字符串的最长递增子序列的长度样例输入 3 aaa ababc abklmncdefg 样例输
算法:单调递增最长子序列
设计一个O(n2)时间的算法,找出由n个数组成的序列的最长单调递增子序列。 输入格式: 输入有两行: 第一行:n,代表要输入的数列的个数 第二行:n个数,数字之间用空格格开 输出格式: 最长单调递增子序列的长度 输入样例: 在这里给出一组输入。例如: 5 1 3 5 2 9 输出样例: 在这里给出相应的输出。例如: 4 #include us
动态规划求最长递增子序列(longest increasing subsequence)
1,什么是动态规划? 在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。当然,各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展,当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线,这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段
中最长的单调递减(或递增)子序列
摘要: 问题描述:给出一个数列,找出其中最长的单调递减(或递增)子序列。解题思路:动态规划。假设0到i-1这段数列的最长递减序列的长度为s,且这些序列们的末尾值中的最大值是t。对于a[i]有一下情况:(1)如果a[i]比t小,那么将a[i]加入任何一个子序列都会使0到i的最长单调序列长度变成s+1,这样的话,在0到i的数列中,长度为s+1的递减子序列的末尾值最大值就是a[i];(2)如果a[i]和
7-7 最长连续递增子序列(20 分)
7-7 最长连续递增子序列(20 分) 给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 输入格式: 输入第1行给出正整数n(≤10​5​​);第2行给出n个整数,其间以空格分隔。 输出格式: 在一行中输出第一次出现的最长连续递增子序列,数字之间用空格分隔,序列结尾不能有多...
最长递增子序列(两种时间复杂度算法及其区别)+最长递减子序列(reverse)
O(n*n)//LIS+路径回溯 O(n*n) #include &amp;lt;iostream&amp;gt; #include&amp;lt;cstdio&amp;gt; #include&amp;lt;stack&amp;gt; #include&amp;lt;cstring&amp;gt; using namespace std; const int maxn=100+5; int a[maxn],dp[maxn]; int parent[m...
NYOJ17 单调递增最长子序列(最长单调递增子序列)
题目:单调递增最长子序列时间限制:3000 ms  |  内存限制:65535 KB难度:4描述求一个字符串的最长递增子序列的长度如:dabdbf最长递增子序列就是abdf,长度为4输入第一行一个整数0&amp;lt;n&amp;lt;20,表示有n个字符串要处理随后的n行,每行有一个字符串,该字符串的长度不会超过10000输出输出字符串的最长递增子序列的长度样例输入3 aaa ababc abklmncdefg...
c语言中如何判断一个数组是递增数组
用递归算法判断数组a[N]是否为一个递增数组。 递归的方法,记录当前最大的,并且判断当前的是否比这个还大,大则继续,否则返回false结束: bool fun(int a[], int n) { if(n= =1) return true; if( n= =2 ) return a[n-1] >= a[n-2]; return fun( a,
nyist oj 214 单调递增子序列(二) (动态规划经典)
单调递增子序列(二) 时间限制:1000 ms  |  内存限制:65535 KB 难度:4 描述 给定一整型数列{a1,a2...,an}(0 如:1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13,长度为5。 输入 有多组测试数据( 每组测试数据的第一行是一个整数n表示序列中共有n个整数,随后的下一行里有n个整数,
C++ 给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)输出最长子序列的长度及对应的子序列
Evelyn QQ: 1809335179 给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)输出最长子序列的长度及对应的子序列 #include #include using namespace std; int main() { int T; cin >> T; vector num; vector result; vector out;
最长递增子列、最长公共子序列 python实现
DP算法:最长公共子序列:把问题分成两种情况来讨论:1. 如果S1[i] == S2[j]。就是i,j对应位置上的字符相等。那么可以得出M[i,j] = M[i-1,j-1]+1;为什么呢?可以想象的。如果M[i-1,j-1]也是一个最后方案,在这个最优方案上我们同时增加一个字符。而这两个字符又相 等。那么我们只需要在这个M[i-1,j-1]的最优方案上++就可以了。2. 如果S1[i] != S2[j]。那么就拿M[i-1,j]和M[i,j-1]来比较。M[i,j]的值就是M[i-1,j]和M[i,j-1
求一个数组的最长严格递增子序列
比如输入 8 5 9 4 1 3 7 6 7 输出 4 思想如下(自己不知道怎么说,所以借鉴别人的说法吧): 假设要寻找最长上升子序列的序列是a[n],然后寻找到的递增子序列放入到数组b中。 (1)当遍历到数组a的第一个元素的时候,就将这个元素放入到b数组中,以后遍历到的元素都和已经放入到b数组中的元素进行比较; (2)如果比b数组中的每个元素都大,则将该元素插入到b数组的
NYOJ 17-单调递增最长子序列
点击打开链接 单调递增最长子序列 时间限制:3000 ms  |  内存限制:65535 KB 难度:4 描述求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入第一行一个整数0 随后的n行,每行有一个字符串,该字符串的长度不会超过10000 输出输出字符串的最长递增子序列的长度 样例输入 3 a
最长递增子序列(模板)
最长公共子序列 (模板) 时间复杂度nlog(n);原理解释:我推荐看这篇博客,慢慢理解。#include<cstdio> #include<algorithm> using namespace std; const int maxn=100010; const int inf=0x3f3f3f3f; int a[maxn]; int dp[maxn]; int main() { int
C++计算整数序列的最长递增子序列的长度
给定一个整数序列,计算其中的最长递增子序列的长度,这是一个典型的动态规划的算法。比如8个整数的序列 186 186 150 200 160 130 197 200,最长递增子序列是 150 160 197 200, 长度为4。