【题目描述】
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/
网友评论