https://www.youtube.com/watch?v=CE2b_-XfVDk&t=300s
07/04/2017更新
今天又仔细写了一遍，发现这题昨天还是没想清楚。
昨天我以为， if (nums[i] > nums[j]) 这句决定了dp里面有些位是0的，其实不是的，这个if只是会更新max的值，如果不更新，那dp这一位就等于之前的max的，也正因为如此，max是要在外层for每次右移都更新的。另外也正因为如此，最后返回的结果不能是dp[nums.length-1]。
另外，看了一下第二种方法，二分+一个for循环，但感觉有点tricky，不太好找规律。偷懒了，不写了。
以下讲解摘自：http://www.jianshu.com/p/a3cd9df6d9d1
这种方法的解题步骤是：
-将第1个数字加入解集；
-依次读取后面的数字，如果此数字比解集中最后一个数字大，则将此数字追加到解集后，否则，用这个数字替换解集中第一个比此数字大的数，解集是有序的，因此查找可以用二分法，复杂度O(log n)；
-最后的答案是解集的长度（而解集中保存的并不一定是合法解）。
举个栗子，输入为[1,4,6,2,3,5]：
-解集初始化为[1]；
-读到4，将其追加到解集中，解集变为[1,4]；
-读到6，将其追加到解集中，解集变为[1,4,6]；
-读到2，用其替换解集中的4，解集变为[1,2,6]，注意此时解集不是一个合法解，因为2是在6后出现的，但是解集的长度始终标识着当前最长序列的长度；
-读到3，用其替换解集中的6，解集变为[1,2,3]；
-读到5，将其追加到解集中，解集变为[1,2,3,5]，得到答案为解集长度4。
06/04/2017
LIS问题，老生常谈的一维DP问题了。但是我这题竟然想了很久没想通。最后还看了答案调试了一会儿。有时感觉一维dp比二维dp还要复杂。。或者说因为我脑子现在已经不转了。。好累。这两天好累啊，白天上班晚上上课，尤其上完课大半夜再想这个，脑子已经不怎么转了，很痛苦。我不喜欢这种节奏。很烦。
还有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]，否则下一次循环就乱了
max = Math.max(dp[j] + 1, max);
}
}
dp[i] = max;
res = Math.max(dp[i] , res);
}
return res;
}
