Description

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

注意in[i], de[i]即使不增不减也要给它赋个最小值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[] in = new int[A.length];
        int[] de = new int[A.length];
        in[0] = 1;
        de[0] = 1;
        int max = 1;
        for (int i = 1; i < A.length; i++) {
            in[i] = 1;
            de[i] = 1;
            if (A[i] > A[i - 1]) {
                in[i] = in[i - 1] + 1;
                max = Math.max(max, in[i]);
            } else if (A[i] < A[i - 1]) {
                de[i] = de[i - 1] + 1;
                max = Math.max(max, de[i]);
            }
        }

        return max;
    }
}