Longest Increasing Subsequence

Question

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

For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

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

Solution

自己想沒能想出來。有考慮過是否該用 DP 解，但總覺得自己對 DP 還是沒什麼感覺。naive 解法也是當前的數如果比前一個數來的大，那就可以取或不取。這樣算出來的 time complexity 是 O(2ⁿ)，遠遠大於題目要的 O(nlogn)。

下一步的優化，如果是用 recursion 來解，那就一定會有重複計算的問題。因此，最簡單的 DP 其實就是 recursion with memorization。我們可以建一個 cache[i][j]，代表前 i 個所組成的 LIS，加上當前 position 在 j 時，所能組成的 LIS。

    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0 || nums == null) {
            return 0;
        }

        int[][] cache = new int[nums.length + 1][nums.length];
        for (int[] array : cache) {
            Arrays.fill(array, -1);
        }

        return helper(nums, -1, 0, cache);
    }

    public int helper(int[] nums, int prevIndex, int curIndex, int[][] cache) {
        if (curIndex == nums.length) {
            return 0;
        }

        if (cache[prevIndex + 1][curIndex] >= 0) {
            return cache[prevIndex + 1][curIndex];
        }

        int taken = 0;
        if (prevIndex < 0 || nums[curIndex] > nums[prevIndex]) {
            taken = 1 + helper(nums, curIndex, curIndex + 1, cache);
        }

        int notTaken = helper(nums, prevIndex, curIndex + 1, cache);
        cache[prevIndex + 1][curIndex] = Math.max(taken, notTaken);

        return cache[prevIndex + 1][curIndex];
    }

若單純用 DP 解的話，在當下這個 index i，我們用 j 從頭 iterate 起，如果 nums[j] < nums[i]，那就代表 dp[i] 有可能會是 dp[j] + 1。所以從頭的 iteration，我們可以找到 max dp[j]，因此 dp[i] = max dp[j] + 1。

    if (nums.length == 0 || nums == null) {
            return 0;
        }

        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max = 1;
        for (int i = 0; i < nums.length; i++) {
            int localMax = 0;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    localMax = Math.max(localMax, dp[j]);
                }
            }
            dp[i] = localMax + 1;
            max = Math.max(dp[i], max);
        }
        return max;

如果要試著優化，從 O(n²) 到 O(nlongn)，要馬是排序，要馬是用 logn 的 data structure。用 binarySearch 的思路是，我們試著 maintain 一個 increasing array，試著把 nums[i] 插進或取代 increasing array 裡的元素。最後這個 array 的 length 就會是我們的答案。但要特別注意的是，用這個方法所得到的 array，並不一定會是真正的答案，也就是說，這個方法所建出來的 increasing array 有可能是不存在的，但 length 會是正確的。

    if (nums.length == 0 || nums == null) {
            return 0;
        }

        int len = 0;
        int[] dp = new int[nums.length];
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }

            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;