最长递增子序列

最长递增序列不要求数组元素连续问题,返回递增序列长度和递增序列。o(n^2)做法,顺序比较以第i个元素开头的递增序列即可。

利用动态规划来做,假设数组为1, -1, 2, -3, 4, -5, 6, -7。我们定义LIS[N]数组,其中LIS[i]用来表示以array[i]为最后一个元素的最长递增子序列。

使用i来表示当前遍历的位置:

当i = 0 时,显然,最长的递增序列为(1),则序列长度为1。则LIS[0] = 1

当i = 1 时,由于-1 < 1,因此,必须丢弃第一个值,然后重新建立序列。当前的递增子序列为(-1),长度为1。则LIS[1] = 1

当i = 2 时,由于2 > 1,2 > -1。因此,最长的递增子序列为(1, 2),(-1, 2),长度为2。则LIS[2] = 2。

当i = 3 时,由于-3 < 1, -1, 2。因此,必须丢掉前面的元素,重建建立序列。当前的递增子序列为(-3),长度为1。则LIS[3] = 1。

依次类推之后,可以得出如下结论。

LIS[i] = max{1, LIS[k] + 1}, array[i] >array[k], for any k < i

最后,我们取max{Lis[i]}。

  #include<stdio.h>
  #include<iostream>
  using namespace std;
  void FindLongestAscSequence(int *input,int size){
      int *list = new int[size];// 用来存储以第i个元素结尾的最长递增子序列
      int MaxLen = 1;
      int k = 0;
      for (int i = 0; i < size; i++){
          list[i] = 1 ;0         for ( int j = 0; j < i; j++){
             if ((input[i] > input[j]) && (list[j] +1 > list[i]) )
                    list[i] = list[j] + 1;
         }
         if (MaxLen < list[i]){
             MaxLen = list[i];
         }
     }
     cout<<MaxLen<<endl;
 }
 int main(){
     int test1[] = {5,-1,-2,4,9,1};
     int test2[] = {1,2,3,4,5,6};
     int test3[] = {6,5,4,3,2,1};
     FindLongestAscSequence(test1,6);
     FindLongestAscSequence(test2,6);
     FindLongestAscSequence(test3,6);
     return 0;
 }

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-08-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏和蔼的张星的图像处理专栏

547. 两数组的交

样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].要求去重,这样还是稍微有点难度。

582
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题15求链表中倒数第K个结点

算法的分析过程均在代码注释中: /** * 题目:输入一个单链表,输出该链表从后往前的第k个数。 * PS:从后往前数时从1开始计数。 * @author...

2806
来自专栏ACM算法日常

分割排序(排序)- HDU 1106

输入一行数字,如果我们把这行数字中的‘5’都看成空格,那么就得到一行用空格分割的若干非负整数(可能有些整数以‘0’开头,这些头部的‘0’应该被忽略掉,除非这个整...

551
来自专栏小樱的经验随笔

COGS 1299. bplusa【听说比a+b还要水的大水题???】

1299. bplusa ☆   输入文件:bplusa.in   输出文件:bplusa.out 评测插件 时间限制:1 s   内存限制:128 MB ...

2708
来自专栏C语言及其他语言

[蓝桥杯]字符逆序

题目描述 将一个字符串str的内容颠倒过来,并输出。str的长度不超过100个字符。 输入 输入包括一行。 第一行输入的字符串。 输出 输出转换好的逆序字符串。...

3335
来自专栏xingoo, 一个梦想做发明家的程序员

【前端开发系列】—— 利用选择器添加内容

  上文讲到了CSS3的选择器,通过after和before选择器,在元素前后添加内容。   也可以通过变量来实现自定义的标题 1     h1:before{...

1815
来自专栏desperate633

LintCode 二分查找题目分析代码

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组...

712
来自专栏wym

18年暑假多校赛第一场 1002

http://acm.hdu.edu.cn/showproblem.php?pid=6299

621
来自专栏流柯技术学院

正则中需要转义的特殊字符

832
来自专栏软件开发 -- 分享 互助 成长

字符串处理技巧

1、快速统计字符串中每个字符出现的个数 hash表 2、求两个字符串公共的最长子串长度和子串 双重循环遍历找到长度,同时用二重指针保留住最长长度时候的指针位置 ...

1786

扫码关注云+社区