最长递增子序列

最长递增序列不要求数组元素连续问题,返回递增序列长度和递增序列。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++对bool operator < (const p &a)const的认识,运算符重载详解(杂谈)

下面来进行这段代码的分析: struct node {  //定义一个结构体node(节点) int x; int y; int len;   //nod...

3306
来自专栏静默虚空的博客

[Java 基础]方法

方法的定义 Java方法是语句的集合,它们在一起执行一个功能。 方法是解决一类问题的步骤的有序组合 方法包含于类或对象中 方法在程序中被创建,在其他地方被引用 ...

1937
来自专栏从流域到海域

Python 迭代(iteration)

对一组数据进行遍历访问称为迭代(iteration)。 迭代是Python高级特性之一,而且Python的迭代比其他语言更为简便。但是请注意,迭代操作...

1856
来自专栏C#

C#泛型方法解析

    C#2.0引入了泛型这个特性,由于泛型的引入,在一定程度上极大的增强了C#的生命力,可以完成C#1.0时需要编写复杂代码才可以完成的一些功能。但是作为开...

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

【Java学习笔记之三】java中的变量和常量

变量和常量     在程序中存在大量的数据来代表程序的状态,其中有些数据在程序的运行过程中值会发生改变,有些数据在程序运行过程中值不能发生改变,这些数据在程序中...

2816
来自专栏运维技术迷

连仕彤博客[Python笔记] isinstance() 函数

isinstance() 函数来判断一个对象是否是一个已知的类型,类似 type()。但是isinstance和type是有区别的:

491
来自专栏我有一个梦想

C++服务器开发之基于对象的编程风格

Thread.h #ifndef _THREAD_H_ #define _THREAD_H_ #include <pthread.h> #include <b...

19710
来自专栏深度学习与计算机视觉

算法-字符串替换空格

题目: 实现一个函数,把字符串中的每一个空格替换成”%20”。例如输入”We are happy.”,则输出”We%20are%20happy.”。 解题思...

2276
来自专栏mukekeheart的iOS之旅

OC学习3——C语言特性之指针

1、指针是C语言中的一个非常重要的概念,实际上,OC系统类的变量、自定义类的变量等都是指针。定义指针变量的语法格式如下,其中*代表一个指针变量,整个语法代表定义...

2428
来自专栏Deep learning进阶路

Python随记(二)字符串

Python随记(二)字符串 1、  字符串的基本操作 字符串string,也是序列(sequence)的一种,所以所有标准的序列操作:索引、分片、乘法、判断成...

1850

扫码关注云+社区