C++计算整数序列的最长递增子序列的长度操作

给定一个整数序列，计算其中的最长递增子序列的长度，这是一个典型的动态规划的算法。

比如8个整数的序列 186 186 150 200 160 130 197 200，最长递增子序列是 150 160 197 200, 长度为4。

想要解决此问题，可以把这个大问题分解为小问题，依次考虑每个数，计算出包含该数数和该数之前的所有数的最长递增子序列的长度，计算出的长度值作为该数的对应值记录下来，最后可以得到这8个数对应的长度值序列，也是8个数，找到这8个数中的最大值就是所有书的最长递增子序列的长度。

或者也可以这样想，想要计算8个数的最长递增子序列的长度有难度，不如先考虑最简单的情况。只有一个数的时候，最长递增子序列长度就是1；当有两个数时，只考虑第一个数和它以前的数的最长递增子序列就是1，考虑第二个数时只需要找到它之前的所有数中比第二个数小的所有数中最长递增子序列的长度最大值然后加一 ，就是第二个数的长度。

下面给出实现代码：

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
int findLoogestIncreaseSeq(vector<int> &vect)
{
 int len = 0;
 int *count = new int[vect.size()];
 for (int i = 0; i < vect.size(); i++)
 count[i] = 1;
 for (int i = 0; i < vect.size(); i++)
 {
 for (int j = i - 1; j >= 0; j--)
 {
 if (vect[j] < vect[i] && count[j] >= count[i])
 {
 count[i] = count[j] + 1;
 }
 }
 if (count[i] > len)
 len = count[i];
 }
 delete [] count;
 return len;
}
int main()
{
 vector<int> vect;
 int temp;
 while (cin >> temp)
 {
 vect.push_back(temp);
 }
 cout << findLoogestIncreaseSeq(vect) << endl;
 return 0;
}

补充知识：C++ 求最长递增子序列（动态规划）

i 0 1 2 3 4 5 6 7 8
a[i] 1 4 7 2 5 8 3 6 9
lis[i] 1 2 3 2 3 4 3 4 5

时间复杂度为n^2的算法：

//求最长递增子序列
//2019/2/28
#include<iostream>
using namespace std;
int LIS(int a[],int N)
{
 int lis[100] = {};
 for(int i =0;i<N;i++)//给每一个数的lis赋初值为1
 {
  lis[i]=1;
 }
 for(int i = 1;i<N;i++)
 {
  for(int j =0;j<i;j++)
  {
   if(a[j]<a[i]&&lis[j]<lis[i]+1) //找出当前元素前面比它小的元素，比较其lis值
    lis[i] = lis[j] + 1;
  }
 }
 int max = lis[0];
 for(int i =1;i<N;i++)
 {
  if(lis[i]>max)
   max = lis[i];   //找出lis数组中最大值，即最长有序子序列的长度
 }
 return max;
}
int main()
{
 int N;
 int a[100];
 while(cin>>N)
 {
  for(int i = 0;i<N;i++)
   cin>>a[i];
  cout<<LIS(a,N)<<endl;
 }
 return 0;
}

以上这篇C++计算整数序列的最长递增子序列的长度操作就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • C++11用两个线程轮流打印整数的实现方法

    使用C++11标准的的线程语法,用两个线程轮流打印整数,一个线程打印奇数,一个线程打印偶数.可以练习线程的基本操作.线程锁和条件变量等技术.完整代码如下.代码后面附有主要语句的讲解. #include <thread> #include <iostream> #include <mutex> #include <condition_variable> std::mutex data_mutex; std::condition_variable data_va

  • C++ 字符串string和整数int的互相转化操作

    C++ 字符串string和整数int的互相转化操作

    一.string转int的方式 1.采用最原始的string, 然后按照十进制的特点进行算术运算得到int,但是这种方式太麻烦,这里不介绍了. 2.采用标准库中atoi函数. string s = "12"; int a = atoi(s.c_str()); 对于其他类型也都有相应的标准库函数,比如浮点型atof(),long型atol()等等. 3.采用sstream头文件中定义的字符串流对象来实现转换. istringstream is("12"); //构造输

  • C++整数常量的前缀和后缀的示例代码

    这篇文章给大家介绍了C++整数常量的前缀和后缀的示例代码,详情如下所示: 在C/C++中,整数常量可以加上不同的前缀,表示不同的进制: 十进制:不带前缀,默认表示为十进制 八进制:0 表示八进制 十六进制:0x 或 0X 表示十六进制 整数常量还可以加上不同的后缀,表示不同的数据类型: 无符号:U 长整数:L 示例代码如下: #include <iostream> using namespace std; int main() { int x = 666; // 十进制 int y = 020

  • C++实现正整数的四则运算表达式

    本文实例为大家分享了C++正整数的四则运算表达式的具体代码,供大家参考,具体内容如下 设计程序,用户输入一个正整数的四则运算表达式的字符串,输出相应的运算结果. (假设每个字符串表达式只有一个运算符,且是合法的) 如: 输入字符串23+54,则输出77,如果是整数除法,只需输出商即可. #include <iostream> #include <cstdio> using namespace std; int main() { int i, j, k, len = 0, lenf

  • C++计算整数序列的最长递增子序列的长度操作

    给定一个整数序列,计算其中的最长递增子序列的长度,这是一个典型的动态规划的算法. 比如8个整数的序列 186 186 150 200 160 130 197 200,最长递增子序列是 150 160 197 200, 长度为4. 想要解决此问题,可以把这个大问题分解为小问题,依次考虑每个数,计算出包含该数数和该数之前的所有数的最长递增子序列的长度,计算出的长度值作为该数的对应值记录下来,最后可以得到这8个数对应的长度值序列,也是8个数,找到这8个数中的最大值就是所有书的最长递增子序列的长度. 或

  • 求数组中最长递增子序列的解决方法

    存储扩展算法n2编程c 写一个时间复杂度尽可能低的程序,求一个一维数组(N个元素)中的最长递增子序列的长度.例如:在序列1,-1,2,-3,4,-5,6,-7中,其最长的递增子序列为1,2,4,6 或者 -1,2,4,6.(编程之美P198-202)分析与解法根据题目的要求,求一维数组中的最长递增子序列,也就是找一个标号的序列b[0],b[1],-,b[m](0 <= b[0] < b[1] < - < b[m] < N),使得array[b[0]]<array[b[1

  • LIS 最长递增子序列 Java的简单实现

    今天遇到了一个求最长递增子序列的问题,看了之后就尝试着用Java实现了一下,关于什么是最长递增子序列,这里就不在赘述,可以百度或者Google之,以下为实现的代码: 说明:本段代码实现的功能为 (1)随机生成一个有10个元素的数组,然后输出它的最长递增子序列 (2)输出以其中某一个元素为结尾的最长递增子序列的长度 具体的实现思路在注释中已经详细表明了,比较简单,这里就不再赘述 import java.util.Arrays; import java.util.Random; public cla

  • C语言实现最长递增子序列问题的解决方法

    本文实例展示了C语言实现最长递增子序列问题的解决方法.分享给大家供大家参考.具体方法如下: 问题描述: 给定一个序列,找出其最长递增子序列长度. 比如 输入 1 3 7 5 输出 3 算法解决思路: 利用动态规划的思想,以序列的每个点最为最右端,找出每个点作为最右端时的子序列长度的最大值,即问题的求解.因此,在计算前面的每个点的时候,将其结果保存下来,后面的点与前面的点的数值进行比较,如果大,则在其长度基础上加1,并且找出所有可能情况下最长的保存为当前点的长度.形成递归. 具体实现代码如下: #

  • C++ LeetCode300最长递增子序列

    目录 LeetCode 300.最长递增子序列 方法一:动态规划 AC代码 C++ LeetCode 300.最长递增子序列 力扣题目链接:leetcode.cn/problems/lo… 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度. 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序.例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列. 示例 1: 输入:nums = [10,9,2,5,3,7,101,18]输出:4

  • Java算法之最长公共子序列问题(LCS)实例分析

    Java算法之最长公共子序列问题(LCS)实例分析

    本文实例讲述了Java算法之最长公共子序列问题(LCS).分享给大家供大家参考,具体如下: 问题描述:一个给定序列的子序列是在该序列中删去若干元素后得到的序列.确切地说,若给定序列X= { x1, x2,-, xm},则另一序列Z= {z1, z2,-, zk}是X的子序列是指存在一个严格递增的下标序列 {i1, i2,-, ik},使得对于所有j=1,2,-,k有 Xij=Zj.例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,

  • javascript实现最长公共子序列实例代码

    javascript实现最长公共子序列实例代码

    介绍 最长公共子序列(Longest Common Subsequence LCS)是从给定的两个序列X和Y中取出尽可能多的一部分字符,按照它们在原序列排列的先后次序排列得到.LCS问题的算法用途广泛,如在软件不同版本的管理中,用LCS算法找到新旧版本的异同处;在软件测试中,用LCS算法对录制和回放的序列进行比较,在基因工程领域,用LCS算法检查患者DNA连与键康DNA链的异同;在防抄袭系统中,用LCS算法检查论文的抄袭率.LCS算法也可以用于程序代码相似度度量,人体运行的序列检索,视频段匹配等

  • Python求两个字符串最长公共子序列代码实例

    一.问题描述 给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence).比如字符串1:BDCABA:字符串2:ABCBDAB.则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 二.算法求解 这是一个动态规划的题目.对于可用动态规划求解的问题,一般有两个特征:①最优子结构:②重叠子问题 ①最优子结构 设X=(x1,x2,...,xn)和Y=(y1,y2,...,ym)是两个序列,将X和Y的最长公共子序列记为LCS(X,Y) 找出LCS(X

  • C++动态规划实现查找最长公共子序列

    C++动态规划实现查找最长公共子序列

    目录 最长公共子序列 代码实现 结果 最长公共子序列 最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题.一个数列 ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则称为已知序列的最长公共子序列. 动态规划: 采用二维数组flag来记录下标i和j的走向.数字"1"表示,斜向下:数字"2"表示,水平向右:数字"3"表示,竖直向下 问题描述: 设有字符串a[0…n],b[0…m]

  • python实现整数序列求和

    python实现整数序列求和

    目录 python整数序列求和 python常用的序列求和方法 python整数序列求和 整数序列求和,用户输入一个正整数N,计算从1到N(包含1和N)相加之后的结果. 代码如下: n=input("请输入整数N:") sum=0 for i in range(int(n)): sum+=i+1 print("1到N求和结果:",sum) 运行结果: python常用的序列求和方法 输入正整数n,输出1+2+3+……+n-1+n的和 函数求和 n = int(inp

随机推荐