最长递增子序列

最长递增序列不要求数组元素连续问题,返回递增序列长度和递增序列。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 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【编程基础】C语言复合赋值运算符

在C语言的赋值中有一种特殊的赋值运算符,就是复合赋值运算符。复合赋值运算符就是在赋值符“=”之前加上其它二目运算符可构成。比如大家可能最常看到这样的语句: n ...

2676
来自专栏cloudskyme

jquery clone()表格之后查找里边的元素

clone() 克隆匹配的DOM元素并且选中这些克隆的副本。 在想把DOM文档中元素的副本添加到其他位置时这个函数非常有用。 要做到动态添加表格,并且添加后修改...

3275
来自专栏漫漫深度学习路

c++复杂声明

void (*funcPtr)(); 上面声明了一个指向函数的指针,当碰到这样一个比较复杂的声明时,最好的方法是从 中间开始和向外扩展: 从中间开始:即 从变量...

1687
来自专栏康怀帅的专栏

Redis set 类型

从集合 (set) 中插入或者删除元素,set 中不能有重复值 sadd set1 12 13 14 移除 srem set1 12 13 集合元素数量 sca...

3384
来自专栏运维技术迷

PHP-数组排序

分别定义一个数值数组和一个关联数组. $age=array("lili"=&gt;"23","bob"=&gt;"30","ben"=&gt;"44"); $c...

2806
来自专栏PHP技术

PHP知识点

JSON支持 包括json_encode(), json_decode()等函数,JSON算是在web领域非常实用的数据交换格式,可以被JS直接支持,JSON实...

3286
来自专栏Golang语言社区

Golang语言社区--【基础知识】范围规则

在任何编程程序的作用域,其中一个定义的变量可以有它的存在,超出该变量的区域就不能访问。有三个地方变量可以在Go编程语言声明如下: 内部函数或这就是所谓的局部变量...

31414
来自专栏林冠宏的技术文章

C/C++ char a[ ] 和 char *a 的差别,改变 char *a爆内存错误的原因

对于一些需要传入参数为 char * temp 指针类的函数; 我们定义一个 char a[10] 或char *a 传进去都是可以的。 但是, 如果该函数是会...

16710
来自专栏运维技术迷

Python获得13位unix时间戳

Python中的time模块把datetime时间转换为10位的时间戳,之前有记录过转换的方法。而今天调用的API中需要的是13位(一般Java里默认是13位(...

2905
来自专栏从流域到海域

Python sorted()函数

Python sorted()函数 list内置一个方法sort(),可以实现对list内的元素做排序。 Python中提供sorted()高级...

1686

扫描关注云+社区