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

示例:

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

• 可能會有多種最長上升子序列的組合，你只需要輸出對應(yīng)的長度即可。
• 你算法的時間復(fù)雜度應(yīng)該為 O(n2) 。

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

簡單解法

從動態(tài)規(guī)劃的角度思考，可以開辟一個數(shù)組保存原數(shù)組每個位置的最長上升子序列的長度。當遍歷到原數(shù)組的位置時，在當前位置向前找到比當前值小的最大上升子序列的長度的長度，可能有點繞。
比如在[10,9,2,5,3,7,101,18] 中，遍歷到7位置時，在7之前5和3的最長上升子序列的長度都是2，且都比7小，那么7這個位置的最長上升子序列的長度就是3了 。
dp[i] = Math.max(dp[j] + 1, dp[i]);

完整代碼：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0 || n == 1) {
            return n;
        }

        int[] dp = new int[n];
        dp[0] = 1;

        int res = 0;

        for (int i = 1; i < n ; ++i) {
            dp[i] = 1;

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

            res = Math.max(res, dp[i]);
        }

        return res;
    }
}

優(yōu)化做法

優(yōu)化好的時間復(fù)雜度是O(nlogn), 從時間復(fù)雜度的要求上來看，做內(nèi)層循環(huán)時可以使用二分查找，正好滿足優(yōu)化后的要求，那么問題來了，一個完全無序的數(shù)組怎么使用二分查找？下面分析一下。
數(shù)組：[10,9,2,5,3,7,101,18]

• 第一次遍歷 10, ==> dp[0] = 1;
• 第二次遍歷 10, 9 ==> dp[1] = 1;
• 第三次遍歷 10, 9, 2 ==> dp[2] = 1;
• 第四次遍歷 10, 9, 2, 5 ==> dp[3] = 2;
• 第五次遍歷 10, 9, 2, 5, 3 ==> dp[4] = 2;
  不知道各位觀察到規(guī)律沒有，第一次遍歷、第二次遍歷和第三次遍歷的結(jié)果都是1，第四次遍歷結(jié)果是2，只要第三次之后的結(jié)果比2大，那么結(jié)果就是2，這樣的話10和9，對我們來說就沒有意義了。如果去掉10和9，后續(xù)是2, 5, 3，如果下一個值是4，那么結(jié)果是3，5也就沒必要保留了，這樣剩下2和3 ，就是一個有序的數(shù)組了。

也就是說在相同結(jié)果長度的情況下，我們每個位置都保留最小的數(shù)組值，這樣就會生成一個有序的數(shù)組，就可以使用二分查找了。

下面上代碼

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0 || n == 1) {
            return n;
        }

        int[] dp = new int[n + 1];

        // 保證原數(shù)組中的每次元素都比新數(shù)組初始位置的大
        dp[0] = Integer.MIN_VALUE;

        int top = 0;
        int j = 0, end = 0, low = 0;


        for (int i = 0; i < n ; ++i) {
            low = 0;
            end = top;

            // 二分查找 找到dp數(shù)組中第一個小于 nums[i]的位置
            while (low <= end) {
                int mid = (low + end) / 2;
                if (dp[mid] < nums[i]) {
                    j = mid;
                    low = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            
            //  dp數(shù)組中第一個小于 nums[i]的位置 后一個位置賦值為nums[i]
            dp[j + 1] = nums[i];

            // 因為會替換dp中的值，所以top保留的就是最長上升子序列的長度
            if (j + 1 > top) {
                top = j + 1;
            } 
            
        }

        return top;
    }
}

完整代碼如上所示，我刷了不少題，但是這道題覺得比較有代表性。