Longest Increasing Continuous Subsequence 397

Question

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.

Solution

从前往后和从后往前各找一次，如果后一个（前一个）比前一个（后一个）大，则将length更新+1，否则将length更新为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;
        }

        if(A.length  == 1){
            return 1;
        }

        int length = 1;
        int max = 0;
        for(int i = 1; i < A.length; i++){
            if(A[i] > A[i - 1]){
                length++;
            }else{
                length = 1;
            }
            max = Math.max(max, length);
        }

        length = 1;
        for(int i = A.length - 2; i >= 0; i--){
            if(A[i] > A[i + 1]){
                length++;
            }else{
                length = 1;
            }
            max = Math.max(max, length);
        }

        return max;
    }
}