Longest Increasing Continuous Subsequence

Problem

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

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.
两个指针就好了，分情况讨论。

Solution

1. Muggle

   public class Solution {

      public int longestIncreasingContinuousSubsequence(int[] A) {
          if (A == null || A.length == 0) return 0;
          if (A.length == 1) return 1;
          int count = 1, countn = 1, max = 0;
          for (int i = 0; i < A.length - 1; i++) {
              if (A[i+1] >= A[i]) {
                  countn = 1;
                  count++;
                  max = Math.max(max, count);
              }
              else {
                  count = 1;
                  countn++;
                  max = Math.max(max, countn);
              }
          }
          return max;
      }

   }

2. DP
   你要的DP，唉

public class Solution {
    public int longestIncreasingContinuousSubsequence(int[] A) {
        // Write your code here
        int len = A.length;
        if (A == null || len == 0) return 0;
        if (A.length == 1) return 1;
        int[] dp = new int[len+1];
        int max = 0;
        dp[0] = 1;
        for (int i = 1; i < len; i++) {
            dp[i] = A[i] > A[i-1] ? dp[i-1] + 1 : 1;
            max = Math.max(max, dp[i]);
        }
        for (int i = 1; i < len; i++) {
            dp[i] = A[i] < A[i-1] ? dp[i-1] + 1 : 1;
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}