本題用動態(tài)規(guī)劃和二分查找可解

一、題目

給定一個無序的整數數組，找到其中最長上升子序列的長度。

示例:

輸入: [10,9,2,5,3,7,101,18]
輸出: 4 
解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。

說明:
可能會有多種最長上升子序列的組合，你只需要輸出對應的長度即可。你算法的時間復雜度應該為 O(n^2) 。

進階:你能將算法的時間復雜度降低到 O(n log n) 嗎?

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-increasing-subsequence

二、分析

2.1 題目分析

原始的數組是一個無序數組，要從無序數組中找到最長上升子序列。這個子序列的元素在原始數組中不要求是連續(xù)的，并且子序列的元素必須是嚴格遞增的。
也就是說如果原始數組是 [10,9,2,5,3,7,101,18]，那么 [2,3,7,101]就是一個最長的上升子序列。

2.2 回溯？

如果我們用回溯法來遍歷數組，時間復雜度是2^n次方，這是不能接收的。

2.3 動態(tài)規(guī)劃

既然題目要求的是最長子序列的長度，那么我們可以使用動態(tài)規(guī)劃，啟動dp[i]保存的就是以第 i個數字結尾的最長子序列的長度。
也就是說，如果原始數組src [] = {10, 3, 5, 2};
則dp[] 應為是 {1, 1, 2, 1}

我們應該把狀態(tài)轉移公式求出來。

動態(tài)規(guī)劃的狀態(tài)轉移方程

基于上面的公式，我們可以寫出下面的代碼

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];  //記錄以第i個數組結尾的最長上升序列
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {  // dp[i] = max(dp[j] + 1) && dp[j] < dp[i] && 0 <= j < i
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

代碼的時間復雜度是 n^2

2.4 動態(tài)規(guī)劃+二分查找

如果將時間復雜度提高到nlogn，那么就需要修改一下思路。
我們用dp[i]保存所有長度為i + 1的上升序列的最后一個元素中最小的那一個。
因此，對于src[] = {10, 9, 2, 5, 3, 7, 101, 18}
遍歷數組，dp對應為

i = 0 dp = {10}
i = 1 dp = {9}
i = 2 dp = {2}
i = 3 dp = {2, 5}
i = 4 dp = {2, 3}
i = 5 dp = {2, 3, 7}
i = 6 dp = {2, 3, 7, 101}
i = 7 dp = {2, 3, 7, 18}

由于dp數組是嚴格上升的，那么我們可以用二分查找的方式更新dp數組，這樣總的時間復雜度就是nlogn。
代碼如下

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length]; // dp[i] 標識所有長度為i+1的序列中，最小的序列尾數
        int maxLen = 1;
        dp[0] = nums[0];
        for (int cur : nums) {
            if (cur > dp[maxLen - 1]) {
                dp[maxLen] = cur;
                maxLen++;
            } else {
                int start = 0;
                int end = maxLen - 1;
                while (start < end) {  //二分查找
                    int mid = (start + end) /2;
                    if (cur > dp[mid]) {
                        start = mid + 1;
                    } else {
                        end = mid;
                    }
                }
                dp[start] = cur;
            }
        }
        return maxLen;
    }