最长上升连续子序列

题意

给定一个整数数组(下标从 0 到 n-1, n 表示整个数组的规模),请找出该数组中的最长上升连续子序列。(最长上升连续子序列可以定义为从右到左或从左到右的序列。)

样例

给定 [5, 4, 2, 1, 3], 其最长上升连续子序列(LICS)为 [5, 4, 2, 1], 返回 4.

给定 [5, 1, 2, 3, 4], 其最长上升连续子序列(LICS)为 [1, 2, 3, 4], 返回 4.

思路

max 存储最大的上升连续子序列 count 记录可能为最大循环子序列的统计 先从左侧开始循环,若当前数大于下一个数,那么 count++,如果 count > max,则将 count 赋值给 max。然后从右侧向左开始循环,同理。

代码实现

public class Solution {
    /*
     * @param : An array of Integer
     * @return: an integer
     */
    public int longestIncreasingContinuousSubsequence(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int max = 1;
        int count = 1;
        for (int i = 0; i < A.length - 1; i++) {
            if (A[i] < A[i + 1]) {
                count++;
            } else {
                count = 1;
            }
            max = count > max ? count : max;
        }
        
        count = 1;
        
        for (int i = A.length-1; i > 0; i--) {
            if (A[i] < A[i - 1]) {
                count++;
            } else {
                count = 1;
            }
            max = count > max ? count : max;
        }
        
        return max;
    }
}

原题地址

LintCode:最长上升连续子序列

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老九学堂

嘀 , 嘀嘀 ... 常用排序算法再总结

  这篇文章中再和小伙伴们来探讨一下常用的非比较排序算法:计数排序,基数排序,桶排序。在一定条件下,它们的时间复杂度可以达到O(n)。

13530
来自专栏mathor

LeetCode164. 最大间距

 这道题用到了桶排序的思想,但是跟排序没啥关系,思路是这样的,数组中有n个元素,那么就构建n+1个桶,桶的属性有三个,最大值最小值以及是否为空。桶的下标从0...

14220
来自专栏公众号_薛勤的博客

让你一看就懂的快速排序算法(Java)

你也许会被快速排序的文章弄得迷迷糊糊,其实大体上去看,快速排序就一步:找个数做基准数,把小于它的数移到它左边,把大于它的数移到它右边。这句话是核心。然后我们只需...

12220
来自专栏编程

python奇遇记:深入的了解函数

很久没更新了,抱歉。最近一段时间忙着对付各种考试,现在总算是考完了,继续来聊聊Python。Python中的函数使用def关键字定义,这个大家都知道,而且Pyt...

183100
来自专栏刘望舒

算法(三)初等排序后篇[选择和希尔排序]

1.选择排序 根据上一篇文章讲到的插入排序和冒泡排序,我们把选择排序的数组也分为已排序部分和未排序部分。 图解选择排序 在用图来讲解选择排序之前,我们要先了...

19480
来自专栏目标检测和深度学习

常用排序算法总结(2)

14440
来自专栏GreenLeaves

JavaScript引用类型之Array数组的排序方法

数组中已经存在两个JavaScript给我们定义好的重排序的方法:reverse()和sort()方法,下面来简单分析下: 1、reverse()    用于反...

21860
来自专栏Python爱好者

Java基础笔记05

17780
来自专栏编程

python学习第二天:python的函数、循环和条件、类

第一天学习了Python的基本操作,以及几种主要的容器类型,今天学习 ,这样才算对Python有一个大致的了解。今天的学习大纲如下: 三、函数 1、定义函数 四...

18260
来自专栏运维技术迷

PHP-数组排序

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

33660

扫码关注云+社区

领取腾讯云代金券