Lintcode 397. Longest Continuous Increasing 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.

Example

Example 1:

Input: [5, 4, 2, 1, 3]
Output: 4
Explanation:
For [5, 4, 2, 1, 3], the LICS  is [5, 4, 2, 1], return 4.

Example 2:

Input: [5, 1, 2, 3, 4]
Output: 4
Explanation:
For [5, 1, 2, 3, 4], the LICS  is [1, 2, 3, 4], return 4.

Challenge

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

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

public class Solution {     /**      * @param A: An array of Integer      * @return: an integer      */     public int longestIncreasingContinuousSubsequence(int[] A) {         return Math.max(findLIC(A, true), findLIC(A, false));     }           private int findLIC(int[] A, boolean inc) {         if (A == null || A.length == 0) {             return 0;         }                   int maxLen = 1;         int len = 1;                   for (int i = 1; i < A.length; i++) {             if (inc) {                 if (A[i] > A[i - 1]) {                     len++;                 } else {                     len = 1;                 }             } else {                 if (A[i] < A[i - 1]) {                     len++;                 } else {                     len = 1;                 }             }                           maxLen = Math.max(maxLen, len);         }                   return maxLen;     } }