力扣300. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

思路1、
用一个数组dp[i]代表前i个数字的最长上升序列，很显然
dp[0] = 1;
dp[i] = Math.max(dp[i],dp[j]+1),其中0<=j<i
代码如下:

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

方法二、dp+二分替换
实际上，我们遍历到的数a[i]只有两种情况
1、a[i]大于最大的数，直接插到dp数组的末位
2、a[i]小于等于最大的数，则替换掉对应的第一个比他大的。
至于第二种情况为什么这样处理，原因是这样的。
第一点，去覆盖掉不会影响所得到的子串的长度
第二点，可以通过替换掉，进行最小数"更新"

比如 1 7 8 2 3 4 5，模拟一下就懂了
代码如下：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if(len <= 1) return len;
        int[] dp = new int[len];
        int pos = 0,max = 0;
        for(int i = 0;i < len;i++){
            pos = Arrays.binarySearch(dp,0,max,nums[i]);
            if(pos < 0){
                pos = -(pos + 1);
            }
            dp[pos] = nums[i];
            if(pos == max){//新加入一个最大的数
                max++;
            }
        }
        return max;
    }
}