LC-300.最长递增子序列

题目描述

leetcode 中等题

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

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

示例1：

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

提示1：

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

动态规划

定义 $dp[i]$ 表示以第 $i$ 个元素结尾的最长子序列长度，有：

$$
\begin{align}
&dp(i) = max\{dp(j)\} + 1　　　　 0 <= j < i　 \&\&　 nums[j] < nums[i]\\
&LIS= max\{dp(i)\}　　　　　　 0 <= i < n
\end{align}
$$

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        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);
                }
            }
        }
        return Arrays.stream(dp).max().orElseThrow() + 1;
    }
}

贪心 + 二分查找

上面解法时间复杂度为 $O(N^2)$ ，另一种更快的解法是贪心 + 二分。

定义 $d[i]$ 表示长度为 $i$ 的子序列的最后一个元素，我们需要让最后一个元素尽量小，从而可以得出 $LIS$。

可知 $d$ 数组是单调递增的，因为假设存在 $dp[i] < dp[j]$ 且 $i > j$，那么该 $i$ 长度的子序列第 $j$ 个元素必然会小于 $d[j]$ ，这与 $d$ 的定义矛盾。

令 $maxLength$ 为当前最大子序列长度，依次遍历 $nums$，具体的 $maxLength$ 维护过程如下：

• 如果当前元素 $nums[i]$ 大于 $d[maxLength]$ ，那么显然有 $d[++maxLength] = nums[i]$
• 如果当前元素 $nums[i]$ 小于等于 $d[maxLength]$ ，为了让 $d$ 的定义正确，需要找到最后一个小于 $nums[i]$ 的 $d[lastLess]$，显然可以得出 $d[lastLess + 1] = nums[i]$。稍微要注意的是这里之所以要找 “第一个小于的下一个坐标” 而不是“第一个大于”的下标，是因为“第一个大于”的下标的前一个元素，即 $d[firstLarge - 1]$ 可能等于 $nums[i]$，而因为题目要求子序列严格递增，所以显然无法由此推出 $d[firstLarge] = nums[i]$。

遍历 $nums$ 的时间复杂度为 $O(N)$，而搜索最后一个小于目标元素的下标可以使用二分查找缩小右边界的方法实现，时间复杂度 $O(logN)$，所以总时间复杂度为 $O(NlogN)$

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] d = new int[n + 1];
        int maxLength = 1;
        d[maxLength] = nums[0];
        for(int i = 1; i < n; i++){
            if(d[maxLength] < nums[i]){
                d[++maxLength] = nums[i];
                continue;
            }
            // Search for the last less than nums[i] index, because question require strictly increasing
            int left = 1, right = maxLength;
            while(left < right){
                int mid = left + (right - left >> 1);
                if(d[mid] < nums[i]){
                    left = mid + 1;
                }else{
                    right = mid;
                }
            }
            d[left] = nums[i];
        }
        return maxLength;
    }
}

// 001011100
// 001110100

01
// 000
// 001 010 011 110 101 111