Longest Increasing Subsequence

Dynamic Programming, Binary Search

Medium

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

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

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

• Your algorithm should run in O(n^2) complexity.

Follow up: Could you improve it to O(nlogn) time complexity?

Analysis

https://leetcode.com/problems/longest-increasing-subsequence/solution/

Naive Approach & Intuition

Brute-Force (TLE) - O(2^n) time

recursively search: include or not include the next position, and find the maximum of them

Recursive with Memoization (MLE)

same as above, but stores intermediate results, thus reduce the repetitive search; however, will exceed memory limit

Dynamic Programming - O(n^2) time, O(n) space

https://leetcode.com/problems/longest-increasing-subsequence/solution/

State:

dp[i] - represents the length of the longest increasing subsequence possible considering the array elements up to the i-th index only, by necessarily including the i-th element.

即以i-th元素结尾，并且包含i-th元素的最长上升子序列的长度

State Transfer Function:

dp[i] = max(dp[j]) + 1,∀ 0 ≤ j < i

To calculate dp[i], we need to append current element (nums[i] ) for all possible nums[i] > nums[j] where j is one of

0, 1, 2, ..., i - 1

Initialization:

dp[0] = 1;

max = 1;

Since single element is considered as LIS of length 1

Final Answer:

LIS_length = max(dp[i]), ∀ 0 ≤ i < n

即循环遍历dp[i]以找到其中最大值

Dynamic Programming with Binary Search - O(nlogn) time, O(n) space

From Source: https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation

@dietpepsi

tails[i] - tails is an array storing the smallest tail of all increasing subsequences with length i+1 in tails[i].

For example, say we have nums = [4,5,6,3], then all the available increasing subsequences are:

len = 1   :      [4], [5], [6], [3]   => tails[0] = 3
len = 2   :      [4, 5], [5, 6]       => tails[1] = 5
len = 3   :      [4, 5, 6]            => tails[2] = 6

Three scenarios on updating the ending (tail) numbers array:

(1) if x is larger than all tails, append it, increase the size by 1
(2) if x is smaller than the tails[0], then update tails[0]
(3) if tails[i-1] < x <= tails[i], update tails[i]

From Source: https://yanjia.me/zh/2018/11/05/70/

按照以下规则更新这些序列 – 如果nums[i]比所有序列的末尾都大，或等于最大末尾，说明有一个新的不同长度序列产生，我们把最长的序列复制一个，并加上这个nums[i]。 – 如果nums[i]比所有序列的末尾都小，说明长度为1的序列可以更新了，更新为这个更小的末尾。 – 如果在中间，则更新那个末尾数字刚刚大于等于自己的那个序列，说明那个长度的序列可以更新了。

Solution

Dynamic Programming - O(n^2) time, O(n) space

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        } 
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < n; i++) {
            int prevMax = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    prevMax = Math.max(dp[j], prevMax);
                }
            }
            dp[i] = prevMax + 1;
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

DP - O(n^2) time, O(n) space -- Easier to understand version

14 ms, faster than 49.36%

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxAns = 1;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxAns = Math.max(maxAns, dp[i]);
        }
        return maxAns;
    }
}

Dynamic Programming with Binary Search - O(nlogn) time, O(n) space

0ms, faster than 100%

class Solution {
    public int lengthOfLIS(int[] nums) {
        // nlogn
        if (nums.length == 0) {
            return 0;
        }
        // `tails[i]` is an array of the ending numbers of LIS with length of i + 1
        int[] tails = new int[nums.length];
        tails[0] = nums[0];
        // `len` means the actual LIS length - 1, it's more convenient for array index
        int len = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > tails[len]) {
                tails[++len] = nums[i];
            } else if (nums[i] < tails[0]) {
                tails[0] = nums[i];
            } else {
                int index = binarySearch(tails, len, nums[i]);
                tails[index] = nums[i];
            }
        }
        return len + 1;
    }
    private int binarySearch(int[] arr, int len, int num) {
        int l = 0, r = len;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (arr[m] < num) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }
}

DP + Binary Search With Comment

public class Solution {
    public int lengthOfLIS(int[] nums) {
        // write your code here
        if(nums.length == 0){
            return 0;
        }
        // len表示当前最长的升序序列长度（为了方便操作tails我们减1）
        int len = 0;
        // tails[i]表示长度为i的升序序列其末尾的数字
        int[] tails = new int[nums.length];
        tails[0] = nums[0];
        // 根据三种情况更新不同升序序列的集合
        for(int i = 1; i < nums.length; i++){
            if(nums[i] < tails[0]){
                tails[0] = nums[i];
            } else if (nums[i] > tails[len]){
                tails[++len] = nums[i];
            } else {
            // 如果在中间，则二分搜索
                tails[binarySearch(tails, 0, len, nums[i])] = nums[i];
            }
        }
        return len + 1;
    }

    private int binarySearch(int[] tails, int min, int max, int target){
        while(min <= max){
            int mid = min + (max - min) / 2;
            if(tails[mid] == target){
                return mid;
            }
            if(tails[mid] < target){
                min = mid + 1;
            }
            if(tails[mid] > target){
                max = mid - 1;
            }
        }
        return min;
    }
}

Reference

LeetCode discussion: https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation

LeetCode Official Solution: https://leetcode.com/problems/longest-increasing-subsequence/solution/

GeeksforGeeks - N log N time: https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

Yanjia: https://yanjia.me/zh/2018/11/05/70/

Grandy Yang: http://www.cnblogs.com/grandyang/p/4938187.html