Longest Increasing Subsequence

Medium Dynamic Programming Binary Search

LintCode: https://www.lintcode.com/en/problem/longest-increasing-subsequence/

LeetCode: https://leetcode.com/problems/longest-increasing-subsequence/#/description

Question

Given an unsorted array of integers, find the length of longest increasing subsequence (LIS).

Notice:
There may be more than one LIS combination, it is only necessary for you to return the length.

Example
Given [10, 9, 2, 5, 3, 7, 101, 18] , The longest increasing subsequence is [2, 3, 7, 101] , therefore the length is 4 .
For [5, 4, 1, 2, 3] , the LIS is [1, 2, 3] , return 3
For [4, 2, 4, 5, 3, 7] , the LIS is [2, 4, 5, 7] , return 4

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.
• https://en.wikipedia.org/wiki/Longest_increasing_subsequence

Challenge

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

Thinking

What is Dynamic Programming?
Breaking a big problems to a collection simpler subproblems. Sovling subproblems and saving result. The result can be used later instead of recomputing subproblem.

To sovle this prolbem, we need create an array to save every number’s LIS. If current number is greater the previous number, current number’s LIS is the max value of current number’s LIS and the previous number’s LIS pluses one. The time complexity is O(n^2)

To achive the O(nlogn), we need to use binary search to find it. THe idea is using an array to store an increasing sequence (NOT a real increasing sequence in the array. ONLY its length is the longest.) Each number looks the closet bigger value than it. If not find, it adds itself at the end. Otherwise, it replaces the big value.

Solution

Java (O(nlogn), binary search, passed on leetcode)

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int lis = 0;
        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int start = 0;
            int end = lis;
            while (start < end) {
                int mid = start + (end - start) / 2;
                if (dp[mid] < nums[i]) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            }
            dp[end] = nums[i];
            if (end == lis) {
                ++lis;
            }
        }
        return lis;
    }
}

Java (O(n^2), passed on lintcode)

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[] lis = new int[nums.length];
        int maxlen = 0;
        for (int i = 0; i < nums.length; i++) {
            ++lis[i];
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if ((lis[j] + 1) > lis[i]) {
                        lis[i] = lis[j] + 1;
                    };
                }
            }
            if (maxlen < lis[i]) {
                maxlen = lis[i];
            }
        }
        return maxlen;
    }
}