题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
在这里插入图片描述
提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：

你可以设计时间复杂度为 O(n2) 的解决方案吗？本解法已达到
你能将算法的时间复杂度降低到 O(n log(n)) 吗?用二分搜索解法

解题思路

首先我们要规定以下dp[i]代表什么含义：dp[i]存放的是：以nums[i]结尾的最长递增子序列的长度。

然后根据这个定义我们可以推出base case: dp[i]的初始值都要为1。因为以nums[i]结尾的最长递增子序列最起码要包含它自己。

由此可以得出算法的过程就是从dp[0]一直演算到dp[i]。那么如何正确的求出dp[i]呢？
假设有一个数组[1,4,3,4,2,3]，我们已经知道dp[0-4]，求出dp[5]。

根据之前的dp[i]的定义可以知道：现在nums[5]=3，我们只需要找到nums[5]前面哪些小于3的子序列，然后把3拼接到那个子序列后面，再给那个子序列的长度+1，就可以了。
当然要注意，可能会拼接出来很多种子序列，，我们只要选择其中最长的那个，然后把拼接后子序列的长度作为dp[5]的值。

用代码来表示就是下面

for (int j = 0; j < i; j++) {
        if (nums[j] < nums[i]) {
            [i] = Math.max(dp[i], dp[j] + 1);
        }
 }

让i=5就是求出dp[5]的值，那么dp[0-4]的求解方式一样，只要让i动起来就可以了。所以稍微改一下代码

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

到这里这题就差不多了。

代码

class Solution {
  public int lengthOfLIS(int[] nums) {
        if (nums.length < 0) {
            return -1;
        }
        if (nums.length == 0) {
            return 0;
        }
        int N = nums.length;
        //dp[i]存放的是：以nums[i]结尾的最长递增子序列的长度
        int[] dp = new int[N];


        //base case：将dp[]都初始化为1
        Arrays.fill(dp, 1);

        for (int i = 0; i < N; i++) {//i=N-1就是dp[]的最后一个元素了，原为dp[]的长度和nums[]的相同
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {//找到比当前值小的，并且在当前值之前出现的值
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int res = 0;
        //来遍历一次经过整理的dp[]，找出最大值
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }

        return res;

    }
}