題目描述：
給定一個(gè)無(wú)序的整數(shù)數(shù)組，找到其中最長(zhǎng)上升子序列的長(zhǎng)度仅政。
示例：
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長(zhǎng)的上升子序列是 [2,3,7,101]育谬，它的長(zhǎng)度是 4狞换。
第 1 步：定義狀態(tài)
由于一個(gè)子序列一定會(huì)以一個(gè)數(shù)結(jié)尾，于是將狀態(tài)定義成：dp[i] 表示以 nums[i] 結(jié)尾的「上升子序列」的長(zhǎng)度坝撑。注意：這個(gè)定義中 nums[i] 必須被選取俐筋，且必須是這個(gè)子序列的最后一個(gè)元素牵素。
第 2 步：考慮狀態(tài)轉(zhuǎn)移方程
遍歷到 nums[i] 時(shí)，需要把下標(biāo) i 之前的所有的數(shù)都看一遍澄者；
只要 nums[i] 嚴(yán)格大于在它位置之前的某個(gè)數(shù)笆呆，那么 nums[i] 就可以接在這個(gè)數(shù)后面形成一個(gè)更長(zhǎng)的上升子序列；
因此粱挡，dp[i] 就等于下標(biāo) i 之前嚴(yán)格小于 nums[i] 的狀態(tài)值的最大者+1赠幕。
語(yǔ)言描述：在下標(biāo) i 之前嚴(yán)格小于 nums[i] 的所有狀態(tài)值中的最大者+1。
符號(hào)描述：
第 3 步：考慮初始化
dp[i] = 1询筏，11 個(gè)字符顯然是長(zhǎng)度為 11 的上升子序列榕堰。
第 4 步：考慮輸出
這里要注意，不能返回最后一個(gè)狀態(tài)值；
還是根據(jù)定義逆屡，最后一個(gè)狀態(tài)值只是以 nums[len - 1] 結(jié)尾的「上升子序列」的長(zhǎng)度圾旨；
狀態(tài)數(shù)組 dp 的最大值才是最后要輸出的值。
第 5 步：考慮狀態(tài)壓縮魏蔗。
遍歷到一個(gè)新數(shù)的時(shí)候砍的，之前所有的狀態(tài)值都得保留，因此無(wú)法壓縮莺治。
改進(jìn)算法:
第 1 步：定義新?tīng)顟B(tài)（特別重要）
tail[i] 表示長(zhǎng)度為 i + 1 的所有上升子序列的結(jié)尾的最小值廓鞠。
說(shuō)明：
tail[0] 表示長(zhǎng)度為 11 的所有上升子序列中，結(jié)尾最小的那個(gè)元素的數(shù)值谣旁，以題目中的示例為例 [10, 9, 2, 5, 3, 7, 101, 18] 中床佳，容易發(fā)現(xiàn)長(zhǎng)度為 2 的所有上升子序列中，結(jié)尾最小的是子序列 [2, 3] 蔓挖，因此 tail[1] = 3
下標(biāo)和長(zhǎng)度有一個(gè) 1 的偏差夕土；
第2步：思考狀態(tài)轉(zhuǎn)移方程
從直覺(jué)上看，tail也是一個(gè)嚴(yán)格上升的數(shù)組瘟判，證明如下：
假設(shè)對(duì)于任意的下標(biāo)i < j怨绣，存在某個(gè)tail[i] >= tail[j]。
對(duì)于此處的tail[i]而言拷获，對(duì)應(yīng)一個(gè)上升子序列[a0,a1,...,ai],依據(jù)定義tail[i] = ai;
對(duì)于此處的tail[j]而言篮撑，對(duì)應(yīng)一個(gè)上升子序列[b0,b1,...,bi,...,bj],依據(jù)定義tail[j] = bj;
由于tail[i] >= tail[j],等價(jià)于ai >= bj，但是bi嚴(yán)格小于bj匆瓜，因此ai >= bj > bi;
然而上升子序列[b0,b1,...bi]是一個(gè)長(zhǎng)度為i + 1但結(jié)尾更小的數(shù)組赢笨，這與ai的最小性相矛盾，證畢驮吱。
算法的執(zhí)行流程
1茧妒、設(shè)置一個(gè)數(shù)組 tail，初始時(shí)為空左冬；
注意：數(shù)組 tail 雖然是有序數(shù)組桐筏，但它不是問(wèn)題中的「最長(zhǎng)上升子序列」（下文還會(huì)強(qiáng)調(diào)），不能命名為 LIS拇砰。有序數(shù)組 tail 只是用于求解 LIS 問(wèn)題的輔助數(shù)組梅忌。
2、在遍歷數(shù)組 nums 的過(guò)程中除破，每來(lái)一個(gè)新數(shù) num牧氮，如果這個(gè)數(shù)嚴(yán)格大于有序數(shù)組 tail 的最后一個(gè)元素，就把 num 放在有序數(shù)組 tail 的后面瑰枫，否則進(jìn)入第 3 點(diǎn)踱葛；
注意：這里的大于是「嚴(yán)格大于」，不包括等于的情況。
3尸诽、在有序數(shù)組 tail 中查找第 1 個(gè)等于大于 num 的那個(gè)數(shù)圾笨，試圖讓它變小逊谋；
如果有序數(shù)組 tail 中存在等于 num 的元素，什么都不做土铺，因?yàn)橐?num 結(jié)尾的最短的「上升子序列」已經(jīng)存在胶滋；
如果有序數(shù)組 tail 中存在大于 num 的元素，找到第 1 個(gè)悲敷，讓它變小究恤，這樣我們就找到了一個(gè)結(jié)尾更小的相同長(zhǎng)度的上升子序列。
說(shuō)明：我們?cè)倏匆幌聰?shù)組 tail[i] 的定義：長(zhǎng)度為 i + 1 的所有最長(zhǎng)上升子序列的結(jié)尾的最小值后德。因此部宿，在遍歷的過(guò)程中，我們?cè)噲D讓一個(gè)大的值變小是合理的瓢湃。
這一步可以認(rèn)為是「貪心算法」理张，總是做出在當(dāng)前看來(lái)最好的選擇，當(dāng)前「最好的選擇」是：當(dāng)前只讓讓第 1 個(gè)嚴(yán)格大于 nums[i] 的數(shù)變小绵患，變成 nums[i]雾叭，這一步操作是“無(wú)后效性”的。
由于是在有序數(shù)組中的操作落蝙，因此可以使用「二分查找算法」织狐。
4、遍歷新的數(shù) num 筏勒，先嘗試上述第 2 點(diǎn)移迫，第 2 點(diǎn)行不通則執(zhí)行第 3 點(diǎn)，直到遍歷完整個(gè)數(shù)組 nums管行，最終有序數(shù)組 tail 的長(zhǎng)度厨埋，就是所求的“最長(zhǎng)上升子序列”的長(zhǎng)度。
第 3 步：思考初始化
dp[0] = nums[0]病瞳，在只有 1 個(gè)元素的情況下揽咕，它當(dāng)然是長(zhǎng)度為 1 并且結(jié)尾最小的元素。
第 4 步：思考輸出
數(shù)組 tail 的長(zhǎng)度套菜，上文其實(shí)也已經(jīng)說(shuō)了亲善，還是依據(jù)定義，tail[i] 表示長(zhǎng)度固定為 i + 1 的所有「上升子序列」的結(jié)尾元素中最小的那個(gè)逗柴，長(zhǎng)度最多就是數(shù)組 tail 的長(zhǎng)度蛹头。
第 5 步：思考狀態(tài)壓縮
無(wú)法壓縮。
作者：liweiwei1419
鏈接：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)渣蜗，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處屠尊。
Java代碼：
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if(len <= 1) return len;
int[] dp = new int[len];
Arrays.fill(dp ,1);
for(int i = 1;i < len;i++) {
for(int j = 0;j < i;j++) {
if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
int res = 1;
for(int i = 0;i < len;i++) res = Math.max(res, dp[i]);
return res;
}
public int lengthOfLISAdvanced(int[] nums) {
int len = nums.length;
if(len < 2) return len;
//tail數(shù)組的定義：長(zhǎng)度為i + 1的上升子序列的末尾最小是幾
int[] tail = new int[len];
//遍歷第一個(gè)數(shù)直接放到tail的開(kāi)頭
tail[0] = nums[0];
//end表示tail的最后一個(gè)已經(jīng)被賦值的元素的索引
int end = 0;
for(int i = 1;i < len;i++) {
//case 1:比tail實(shí)際有效的末尾還大
if(nums[i] > tail[end]) {
//直接添加在那個(gè)元素后面，end先加1
end++;
tail[end] = nums[i];
} else {
//找到第一個(gè)大于等于nums[i]的元素耕拷，嘗試讓該元素更小
int left = 0;
int right = end;
while(left < right) {
int mid = left + ((right - left) >>> 1);
if(tail[mid] < nums[i]) left = mid + 1;
else right = mid;
}
//走到這里是因?yàn)閏ase1的反面讼昆，因此一定能找到一個(gè)大于等于nums[i]的元素
tail[left] = nums[i];
}
}
end++;
return end;
}
}
