Easy
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.
最开始看这道题的时候，被题目说的“Can be from right to left or from left to right”即所谓双向吓到了。就感觉自己得同时更新从左到右的最长和从右到左的最长，这可怎么办思路一下子很混乱。然而LICS的双向仅仅就是表达“既可递增也可以递减”这个意思。所以处理方法很简单，你把递增和递减的最长连续子序列都求出来，最后取一个max就可以了。
最简单的方法是用两个for loop分别求出连续递增子序列的长度和连续递减子序列的长度。注意每次遇到不满足连续递增或递减时，要让lics = 1表示重新计数。 同时要注意求完递增该求递减的时候，一定要reset lics = 1.
public class Solution {
/*
* @param A: An array of Integer
* @return: an integer
*/
public int longestIncreasingContinuousSubsequence(int[] A) {
// write your code here
if (A == null || A.length == 0){
return 0;
}
int lics = 1;
int licsMax = 1;
for (int i = 1; i < A.length; i++){
if (A[i] > A[i - 1]){
lics++;
licsMax = Math.max(licsMax, lics);
} else {
lics = 1;
}
}
lics = 1;
for (int i = 1; i < A.length; i++){
if (A[i] < A[i - 1]){
lics++;
licsMax = Math.max(licsMax, lics);
} else {
lics = 1;
}
}
return licsMax;
}
}
这道题还有动态规划的方法, 实际上思路跟上面的for循环方法是一摸一样的。
public class Solution {
/*
* @param A: An array of Integer
* @return: an integer
*/
public int longestIncreasingContinuousSubsequence(int[] A) {
// write your code here
if (A == null || A.length == 0){
return 0;
}
int n = A.length;
//state:f[x] stands for the LICS at the position i.
int[] f = new int[n];
int max = 1;
int maxReverse = 1;
//function and initialize
f[0] = 1;
for (int i = 1; i < n; i++){
f[i] = A[i] > A[i - 1] ? f[i - 1] + 1 : 1;
max = Math.max(max, f[i]);
}
f[n - 1] = 1;
for (int i = n - 2; i >= 0; i--){
f[i] = A[i] > A[i + 1] ? f[i + 1] + 1 : 1;
maxReverse = Math.max(f[i], maxReverse);
}
//answer
return Math.max(max, maxReverse);
}
}
