Alibi

My Life is Getting Better

Lintcode DP Longest Increasing Continuous Subsequence

18 Dec 2015

###Task1 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. Have you met this question in a real interview? Yes 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.

###Java ####DP

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 left = 1;
        int right = 1;
        int n = A.length;
        //left to right
        int crt = 1;
        for (int i = 1; i < n; i++) {
            if (A[i] > A[i - 1]) {
                crt++;
            } else {
                crt = 1;
            }
            left = Math.max(crt, left);
        }
        
        //right to left
        crt = 1;
        for (int i = 1; i < n; i++) {
            if (A[i] < A[i - 1]) {
                crt++;
            } else {
                crt = 1;
            }
            left = Math.max(crt, left);
        }
        
        return Math.max(left, right);
    }
}

###Points

###Task2

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Have you met this question in a real interview? Yes Example

For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3

For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4

Challenge Time complexity O(n^2) or O(nlogn)

Clarification What’s the definition of longest increasing subsequence?

* The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

###Java

public class Solution {
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    public int longestIncreasingSubsequence(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int left = 0;
        int right = 0;
        //left to right
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] <= nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            left = Math.max(left, dp[i]);
        }
        return left;
    }
}

###Points

Related Posts