1、题目

image.png

2、分析

（1）动态规划：只需要找到转移方程即可。
（2）二分查找法：
本题分析：
https://labuladong.github.io/zgnb/3/15/16/
二分查找法原理：
https://www.cnblogs.com/labuladong/p/12320448.html

3、代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
    // base case：dp 数组全都初始化为 1
    Arrays.fill(dp, 1);
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
          //找到前面比它小的元素
            if (nums[i] > nums[j]) 
                //该元素的最长子序列，等于前面小元素的dp最大值+ 1
                dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
    
    int res = 0;
    for (int i = 0; i < dp.length; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}

二分查找法代码：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int piles = 0;
        int[] arr = new int[nums.length];
        for(int i = 0; i < nums.length; i++){
            int val = nums[i];
            int left = 0;
            int right = piles;
            while(left < right){
                int mid = (left + right) / 2;
                if(arr[mid] == val){
                    right = mid;
                }else if(arr[mid] < val){
                    left = mid + 1;
                }else{
                    right = mid;
                }
            }
            if(left == piles) piles++;
            arr[left] = val;
        }
        return piles;
    }
}