解决思路

动态规划

初始情况下每个元素的LIS值

最后每个元素的LIS值

code

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length==0)
            return 0;
        //memo[i]表示以nums[i]为结尾的最长上升子序列的长度
        int[] memo = new int[nums.length];
        Arrays.fill(memo,1);
        for(int i=1;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i])
                    memo[i] = Math.max(memo[i],1+memo[j]);
            }
        }
        int res = 1;
        for(int i:memo)
            res = Math.max(res,i);
        return res;
    }
}

动态规划+二分查找

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int res = 0;
        for(int num : nums) {
            int i = 0, j = res;
            while(i < j) {
                int m = (i + j) / 2;
                if(tails[m] < num) i = m + 1;
                else j = m;
            }
            tails[i] = num;
            if(res == j) res++;
        }
        return res;
    }
}