[LintCode] Longest Increasing Continuous Subsequence

java 16 2016-02-29 13:03
女装

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;
    }
}
女装
文章评论