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.
Example
For [5, 4, 2, 1, 3], the LICS is [5, 4, 2, 1], return 4.
For [5, 1, 2, 3, 4], the LICS is [1, 2, 3, 4], return 4
这道题跟LeetCode上那道Longest Increasing Subsequence很像，但是比那道题简单，因为这道题需要递增子序列连续，这样我们只要挨个比较一下即可，由于题目中说了左右两个方向递增都行，可以用左右两个方向分别遍历一遍，也可以把两个遍历合并到一起，只用一个循环，同时寻找递增和递减的数列，使用两个变量cnt1和cnt2分别记录最长递增和递减数列的长度，一旦递增递减断开，记得将对应的计数器重置即可，参见代码如下：
class Solution { public: /** * @param A an array of Integer * @return an integer */ int longestIncreasingContinuousSubsequence(vector<int>& A) { if (A.empty()) return 0; int res = 1, cnt1 = 1, cnt2 = 1; for (int i = 0; i < A.size() - 1; ++i) { if (A[i] < A[i + 1]) { ++cnt1; cnt2 = 1; } else { ++cnt2; cnt1 = 1; } res = max(res, max(cnt1, cnt2)); } return res; } };
本文转自博客园Grandyang的博客，原文链接：最长连续递增子序列[LintCode] Longest Increasing Continuous Subsequence ，如需转载请自行联系原博主。
