https://www.youtube.com/watch?v=CE2b_-XfVDk&t=300s
07/04/2017更新
今天又仔細寫了一遍捻激，發(fā)現(xiàn)這題昨天還是沒想清楚凛膏。
昨天我以為庙曙， if (nums[i] > nums[j]) 這句決定了dp里面有些位是0的，其實不是的茂卦，這個if只是會更新max的值豁生，如果不更新，那dp這一位就等于之前的max的捣鲸，也正因為如此瑟匆，max是要在外層for每次右移都更新的。另外也正因為如此栽惶，最后返回的結果不能是dp[nums.length-1]愁溜。
另外，看了一下第二種方法外厂，二分+一個for循環(huán)冕象，但感覺有點tricky，不太好找規(guī)律汁蝶。偷懶了渐扮，不寫了。
以下講解摘自：http://www.reibang.com/p/a3cd9df6d9d1
這種方法的解題步驟是：
-將第1個數(shù)字加入解集穿仪；
-依次讀取后面的數(shù)字席爽，如果此數(shù)字比解集中最后一個數(shù)字大，則將此數(shù)字追加到解集后啊片，否則只锻，用這個數(shù)字替換解集中第一個比此數(shù)字大的數(shù)，解集是有序的紫谷，因此查找可以用二分法齐饮，復雜度O(log n)；
-最后的答案是解集的長度（而解集中保存的并不一定是合法解）笤昨。
舉個栗子祖驱，輸入為[1,4,6,2,3,5]：
-解集初始化為[1]；
-讀到4瞒窒，將其追加到解集中捺僻，解集變?yōu)閇1,4]；
-讀到6，將其追加到解集中匕坯，解集變?yōu)閇1,4,6]束昵；
-讀到2，用其替換解集中的4葛峻，解集變?yōu)閇1,2,6]锹雏，注意此時解集不是一個合法解，因為2是在6后出現(xiàn)的术奖，但是解集的長度始終標識著當前最長序列的長度礁遵；
-讀到3，用其替換解集中的6采记，解集變?yōu)閇1,2,3]佣耐；
-讀到5，將其追加到解集中挺庞，解集變?yōu)閇1,2,3,5]晰赞，得到答案為解集長度4。
06/04/2017
LIS問題选侨，老生常談的一維DP問題了掖鱼。但是我這題竟然想了很久沒想通。最后還看了答案調試了一會兒援制。有時感覺一維dp比二維dp還要復雜戏挡。〕柯兀或者說因為我腦子現(xiàn)在已經不轉了褐墅。。好累洪己。這兩天好累啊妥凳，白天上班晚上上課，尤其上完課大半夜再想這個答捕，腦子已經不怎么轉了逝钥，很痛苦。我不喜歡這種節(jié)奏拱镐。很煩艘款。
還有O(nlogn)的方法，抽空再看了沃琅。哗咆。
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int dp[] = new int[nums.length];
dp[0] = 1;
int res = 1;
for (int i = 1; i < nums.length; i++) {
//max不能是全局的
int max = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
//這里不能就開始改變dp[i]，否則下一次循環(huán)就亂了
max = Math.max(dp[j] + 1, max);
}
}
dp[i] = max;
res = Math.max(dp[i] , res);
}
return res;
}
