Longest Increasing Continuous Subsequence

Lint Source

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

An increasing continuous subsequence:

1. Can be from right to left or from left to right.
2. Indices of the integers in the subsequence should be continuous.

例子：

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.

Note

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

解题思路

public int longestIncreasingContinuousSubsequence(int[] A) {
        if(A == null || A.length ==0)
            return 0;

        boolean ascending = false;
        int start = 0;
        int maxLen = 1;
        for(int i=1;i<A.length;i++) {
            if(A[i] > A[i-1]) {
                if(!ascending) {
                    ascending = true;
                    start = i-1;
                }
            } else if(A[i] < A[i-1]) {
                if(ascending) {
                    ascending = false;
                    start = i-1;
                }
            } else {
                start = i-1;
            }

            maxLen = Math.max(maxLen, i-start+1);
        }

        return maxLen;
}

References

1 solution from Kancloud

2 Longest Increasing Subsequence