Longest Increasing Continuous Subsequence

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.

Notes:

1. DP
2. Function:
   1. f[i] = f[i-1]+1 when nums[i] > nums[i-1]
   2. s[i] = s[i-1]+1 when nums[i] < nums[i-1]
   3. Others: f[i] = s[i] = 1
3. Answer: find the max of f[i] and s[i]

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

        int n = A.length;

        // state
        int[] f = new int[n];
        int[] s = new int[n];

        // initialize
        f[0] = 1;
        s[0] = 1;

        // function
        for (int i = 1; i < n; ++i) {
            if (A[i] > A[i-1]) {
                f[i] = f[i-1]+1;
                s[i] = 1;
            } else if (A[i] < A[i-1]) {
                s[i] = s[i-1]+1;
                f[i] = 1;
            } else {
                s[i] = 1;
                f[i] = 1;
            }
        }

        // answer
        int max = 0;
        for (int i = 0; i < n; ++i) {
            max = Math.max(max, Math.max(s[i], f[i]));
        }

        return max;
    }

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

        int n = A.length;

        int max = 1;
        int ip = 1;
        int dp = 1;

        // function
        for (int i = 1; i < n; ++i) {
            if (A[i] > A[i-1]) {
                ip += 1;
                dp = 1;
            } else if (A[i] < A[i-1]) {
                dp += 1;
                ip = 1;
            } else {
                ip = 1;
                dp = 1;
            }

            max = Math.max(max, Math.max(ip, dp));
        }

        return max;
    }