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

本文实例展示了C语言实现最长递增子序列问题的解决方法。分享给大家供大家参考。具体方法如下：

问题描述：

给定一个序列，找出其最长递增子序列长度。

比如 输入 1 3 7 5

输出 3

算法解决思路：

利用动态规划的思想，以序列的每个点最为最右端，找出每个点作为最右端时的子序列长度的最大值，即问题的求解。因此，在计算前面的每个点的时候，将其结果保存下来，后面的点与前面的点的数值进行比较，如果大，则在其长度基础上加1，并且找出所有可能情况下最长的保存为当前点的长度。形成递归。

具体实现代码如下：

#include "stdio.h"
#include "stdlib.h"
#define MAXDATA 10000
int main(){
  int data[MAXDATA]; /*数据序列*/
  int lgs[MAXDATA];  /*最长子序列长度*/
  int n,temp,k; /*n 序列长度 temp 子序列长度中间变量 */
  scanf("%d",&n);
  if(n>10000){
     return 0;
  }
  for(int i=0;i<n;i++){
    scanf("%d",&data[i]);
  }
  for(int i=0;i<MAXDATA;i++){
    lgs[i]=1;  /*给每一个序列点作为右端时的最大序列长度为1*/
  }
  for(int i=1;i<n;i++){
    temp=1;
    for(int j=0;j<i;j++){ /*与其前面的每一个进行比较*/
      if(data[i]>data[j]){ /*如果数据比前面的某一个的值大*/
        if(lgs[i]+lgs[j]>temp){ /*找出该点的最大子序列长度*/
          temp=lgs[i]+lgs[j];
        }
      }
    }
    lgs[i]=temp;
  }
  temp=lgs[0];
  for(int i=1;i<n;i++){
    if(lgs[i]>temp){
      temp=lgs[i];
    }
  }
  printf("%d",temp);
  system("pause");
}

希望本文所述对大家C程序算法设计的学习有所帮助。

赞 (0)

相关推荐

  • 利用C语言来求最大连续子序列乘积的方法

    利用C语言来求最大连续子序列乘积的方法

    题目描述:给一个浮点数序列,取最大乘积连续子串的值,例如 -2.5,4,0,3,0.5,8,-1,则取出的最大乘积连续子串为3,0.5,8.也就是说,上述数组中,3 0.5 8这3个数的乘积3*0.5*8=12是最大的,而且是连续的. 提醒:此最大乘积连续子串与最大乘积子序列不同,请勿混淆,前者子串要求连续,后者子序列不要求连续.也就是说:最长公共子串(Longest CommonSubstring)和最长公共子序列(LongestCommon Subsequence,LCS)的区别: 子串(S

  • C++动态规划之最长公子序列实例

    本文实例讲述了C++动态规划之最长公子序列解决方法.分享给大家供大家参考.具体分析如下: 问题描述: 求出两个字符串中的最长公子序列的长度. 输入: csblog belong 输出: max length = 4 实现代码: #include <stdio.h> #include <string.h> int arr[200][200]; /* 表示str1的前i位和str2的前j位的最长公子序列的长度 */ int main() { char str1[100],str2[10

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

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

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

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

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

    存储扩展算法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

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

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

  • 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

  • jsp页面中表达式语言中的$符号不起作用的解决方法

    今天myeclipse里部署了之前做的一个测试项目,发现jsp里的$符号tomcat启动后页面上显示出来了,百度搜了下别人也有类似的问题出现过.经提醒原来是web.xml配置的version设置的是2.5而我tomcat5启动的.是tomcat的版本低于web的版本,从而导致$符号不能正常使用. 后将tomcat5改用tomcat6.jdk采用1.6 启动spring2.5项目.$显示问题解决. 以下是网上摘录的详细说明: 在jsp页面中用表达式语言中的$符号,如${pageScope.titl

  • jQueryMobile之窗体长内容的缺陷与解决方法实例分析

    jQueryMobile之窗体长内容的缺陷与解决方法实例分析

    本文实例讲述了jQueryMobile窗体长内容的缺陷与解决方法.分享给大家供大家参考,具体如下: 前面的一篇文章<jQueryMobile之Helloworld与页面切换的方法>没有考虑到窗体中放置长内容的状况 一旦窗体中出现长内容,使用笔者那种固定header与footer的全屏布局是存在缺陷的, 如图所示,长内容最后的内容,直到滚动条拉到最底部也无法穷尽, 而且很有可能的是,虽然现在这个地方的内容是显示为半透明,但往往这个位置是一些提交按钮什么的, 用户根本就没法点, 因此,需要进行改进

  • nodejs发送http请求时遇到404长时间未响应的解决方法

    通常,我们在使用nodejs发送http请求时,一旦遇到404响应,nodejs内部会一直请求下去,直到超出它自己设定的响应时长(最让人恶心的地方就是这个时长还是没法修改的.)很多人在这里碰到了麻烦. 我是在做arcgis地图项目的时候,客户提出需要使用天地图提供的底图服务,当时我直接使用silverlight客户端的Arcgis API进行http请求(同样是内部请求,不开源的东西就是这么让人郁闷),同样碰到了一个进度条一直卡在那的问题.经过调试发现,是由于底图加载请求超时的缘故,和nodej

  • 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,

  • SQL计算字符串中最大的递增子序列的方法

    SQL计算字符串中最大的递增子序列的方法

    求字符串中最大的递增子序列 数据库环境:SQL SERVER 2005 如题,求字符串"abcbklmnodfghijkmer"中最大的递增子序列.这个字符串有点特别, 只由26个小写字母a-z组成. 大概思路如下: 1.将字符串转到一列存储,并生成行号 2.设置一个递增计数器列,默认为1,比较上下行的字符,如果在字典中的顺序是递增, 则计数器加1,否则,计数器置1 3.找出计数器最大的数及对应的行号,根据这2个数截取字符串 思路有了,下面直接贴代码 DECLARE @vtext VA

随机推荐