Lintcode397 Longest Increasing Continuous Subsequence solution 题解
发布在刷题能手——Lintcode 题解2018年4月7日view:217
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Give an integer array,find the longest increasing continuous subsequence in this array.

An increasing continuous subsequence:

Can be from right to left or from left to right.

Indices of the integers in the subsequence should be continuous.

 Notice:O(n) time and O(1) extra space.

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

【注】O(n)的时间和O(1)的额外空间。

【题目链接】

www.lintcode.com/en/problem/longest-increasing-continuous-subsequence/

【题目解析】

题目只要返回最大长度,注意此题中的连续递增指的是双向的,即可递增也可递减。简单点考虑可分两种情况,一种递增,另一种递减,跟踪最大递增长度,最后返回即可。也可以在一个 for 循环中搞定,只不过需要增加一布尔变量判断之前是递增还是递减。

【参考答案】

www.jiuzhang.com/solutions/longest-increasing-continuous-subsequence/

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN
刷题能手——Lintcode 题解

日常更新算法刷题~

我的收藏