動態規劃，二分查找。

題目

由題，從數組中找一個最長子序列，不難想到，當這個子序列遞增子序列的數越接近時是越容易拉長的。從dp上看，當遍歷到這個數，會從前面的dp選一個最大的數加上當前數，注意這里的dp是每遍歷到一個數都會加進去。而這里的dp數組同樣是用來維護到某個數時的ans，nums數組是做了比較的，因此也有可能內循環時數組中的一些數是沒有做更新的，因此最后一步肯定是加上當前的數后再進行一次與更新的dp比較進行選最大。

時間復雜度：O(n^2)，空間復雜度：O(n)。

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

接著是更快的，用二分查找的方法，在用二分時用mid去找目標值。而這里每遍歷到數組的一個數時，同樣可以與tails的數去做比較，注意如果遍歷到的數與dp的數做比較時mid在大的一邊沒有移動過，說明這個數就是大的可以追加到原數組的尾巴，即有位置可以插入。

時間復雜度：O(nlogn)，空間復雜度：O(n)。

class Solution {public int lengthOfLIS(int[] nums) {int[] tails = new int[nums.length];int res = 0;for(int num : nums) {int i = 0, j = res-1;//標準二分，當左右指針重疊時再進行一次比較while(i <= j) {int m = (i + j) / 2;if(tails[m] < num) i = m + 1;else j = m - 1;}//這里的i就是目標值tails[i] = num;//更新這個位置的值if(res == i) res++;//說明可以進行擴充//注意每次找到時res肯定會比i多一，因為res從一開始的}return res;}
}

很典型的一道例題，可以用dp的狀態維護，找到前面的狀態，不過每到一個數都要dp兩次。而二分查找目標值的方法，剛好讓比目標值小的存到tails數組，比tails數組大的直接追加，以此來更新最長遞增子序列。