题目描述

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

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

样例

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

输入：nums = [0,1,0,3,2,3]
输出：4

输入：nums = [7,7,7,7,7,7,7]
输出：1

算法1

(动态规划) $O(n^2)$

状态变量:
变量dp[i] 表示从0 到i 结尾的序列中最长递增子序列的长度

状态计算:
遍历数组nums,每个nums[i] 都作为从[0,i] 子序列的结尾,要从中寻找递增的子序列,那就得满足条件: nums [j] < nums[i] ,0 <= j < i .
为什么j 之与序列的末尾i 进行比较而不与序列中j + 1,j + 2… 等位置进行比较来判断是否是递增序列呢? 因为i 是从0 开始的,那么当前的i 位置必然会成为下一轮i + 1 的循环中的j,也就是成为下一轮循环中的子序列.
如果在当前的循环中判断出[0,j] 是递增序列,并且nums[j] < nums[i],那么dp[i] = dp[j] + 1.

初始条件: dp[i] = 1,代表自身nums[i] 的最基本长度是1

所以dp[i] = Math.max(dp[i],dp[j] + 1);

当遍历nums 数组完成以后,此时的dp 数组中存在以nums[i] (0 <= i <= nums.length - 1)结尾的最长递增序列的长度
所以最后也要遍历dp 数组, 从中找到最长的递增序列的长度.

时间复杂度

O(n^2)

参考文献

Java 代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];

        //枚举[0,i] 中的递增子序列,
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }                
            }
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

算法1

(贪心算法 + 二分查找) $O(nlogn)$

这个思想着实没想到，还是看的别人的解释才能做出来:
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/

时间复杂度

O(nlogn)

参考文献

Java 代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] d = new int[n];
        int end = 0;
        d[end] = nums[0];

        for(int i = 1; i < n; i++){
            if(nums[i] > d[end]){
                d[++end] = nums[i];
            }else{
                int left = 0,right = end;
                while(left < right){
                    int mid = (left + right) >> 1;
                    if(d[mid] >= nums[i]){
                        right = mid;
                    }else{
                        left = mid + 1;
                    }
                }
                d[left] = nums[i];
            }
        }

        return ++end;
    }
}