方法一：动态规划
d[i]: 以第i个元素结尾的最长上升子序列的长度
复杂度：O(N2)
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if(len ==0) return 0;
int[] res = new int[len];
int max=1;
//init
Arrays.fill(res,1);
for(int i=1;i<len;i++){
for(int j=0;j<i;j++){
if(nums[j]<nums[i]){
res[i]=Math.max(res[i],res[j]+1);
max= Math.max(max,res[i]);
}
}
}
return max;
}
}
方法二：贪心（栈+二分搜索）
用在只需要求个数，不需要输出结果的情况中
并不是严格意义上的栈，只是看起来像，用栈维护一个上升子序列
思想：
① 栈的长度表示到目前为止最长子序列的长度
② 下一个元素如果大于当前栈的最大元素，则入栈
③ 如果小于的话，则采用二分查找的方法，查找比当前元素x大的第一个元素y并替换他（
y的存在可能会让后面有新的结果，x对后续的结果没有影响，当全部替换一遍的时候，表示新的结果有效，不然往里面添加元素的时候就是在之前长度的基础上进行添加）
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length == 0) return 0;
int[] up = new int[nums.length];
int index = -1;
up[++index]=nums[0];
for(int i=1;i<nums.length;i++){
if(nums[i]>up[index]){
up[++index] = nums[i];
}
else if(nums[i]<up[index]){
int pos = Arrays.binarySearch(up, 0,index+1, nums[i]); //如果找不到，返回的是负数，且从-1开始
if(pos<0){
up[-pos-1]=nums[i];
}
}
}
return index+1;
}
}
