今天分享的题目来源于 LeetCode 第 300 号问题：最长上升子序列。这道题在 腾讯 笔试中出现过 3 次。

题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

• 你算法的时间复杂度应该为 O(n ² ) 。

进阶: 你能将算法的时间复杂度降低到 O(nlog n) 吗?

题目解析

首先仔细审题，明确题目中的条件。

1、子序列：不要求连续子序列，只要保证元素前后顺序一致即可；

2、上升：这里的“上升”是“严格上升”，类似于 [2, 3, 3, 6, 7] 这样的子序列，因为 3 重复了，所以不是“严格上升”的。

一个序列可能有多个最长上升子序列，题目中只要我们求这个最长的长度。如果使用回溯搜索，选择所有的子序列进行判断，时间复杂度为 𝑂((2^𝑛)∗𝑛)。

这个问题具有最优子结构，因此可以考虑使用动态规划完成。

方法一：动态规划

定义状态： dp[i] 表示以第 i 个数字为结尾的最长上升子序列的长度。即在 [0, ..., i] 的范围内，选择 以数字 nums[i] 结尾 可以获得的最长上升子序列的长度。注意：以第 i 个数字为结尾，即 要求 nums[i] 必须被选取 。反正一个子序列一定会以一个数字结尾，那我就将状态这么定义，这一点是常见的。

状态转移方程：遍历到索引是 i 的数的时候，我们应该把索引是 [0, ... ,i - 1] 的 dp 都看一遍，如果当前的数 nums[i] 严格大于之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列。把前面的 i 个数都看了， dp[i] 的值就是它们的最大值加 1 。即比当前数要小的那些里头，找最大的，然后加 1 。

于是状态转移方程是： dp(i) = max{1 + dp(j) if j < i and dp[i] > dp[j]} 。

最后不要忘了，扫描一遍这个 dp 数组，其中最大值的就是题目要求的最长上升子序列的长度。

Python 代码：

class Solution:

    # 将 dp 数组定义为：以 nums[i] 结尾的最长上升子序列的长度
    # 那么题目要求的，就是这个 dp 数组中的最大者
    # 以数组  [10, 9, 2, 5, 3, 7, 101, 18] 为例
    # dp 的值：1  1  1  2  2  3  4    4

    def lengthOfLIS(self, nums):
        size = len(nums)
        # 特判
        if size <= 1:
            return size

        dp = [1] * size
        for i in range(1, size):
            for j in range(i):
                if nums[i] > nums[j]:
                    # + 1 的位置不要加错了
                    dp[i] = max(dp[i], dp[j] + 1)
        # 最后要全部一看遍，取最大值
        return max(dp)

Java 代码：

import java.util.Arrays;

public class




    
 Solution {

    //【关键】将 dp 数组定义为：以 nums[i] 结尾的最长上升子序列的长度
    // 那么题目要求的，就是这个 dp 数组中的最大者
    // 以数组  [10, 9, 2, 5, 3, 7, 101, 18] 为例：
    // dp 的值：1  1  1  2  2  3  4    4
    // 注意实现细节。
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        // 状态的定义是：以 i 结尾的最长上升子序列的长度
        // 状态转移方程：之前比最后那个数字小的最长上升子序列的长度 + 1
        int[] dp = new int[len];
        // 如果只有 1 个元素，那么这个元素自己就构成了最长上升子序列，所以设置为 1 是合理的
        Arrays.fill(dp, 1);
        // 从第 2 个元素开始，逐个写出 dp 数组的元素的值
        for (int i = 1; i             int curVal = nums[i];
            // 找出比当前元素小的哪些元素的最小值
            for (int j = 0; j                 if (curVal > nums[j]) {
                    dp[i] = Integer.max(dp[j] + 1, dp[i]);
                }
            }
        }
        // 最后要全部走一遍，看最大值
        int res = dp[0];
        for (int i = 0; i             res = Integer.max(res, dp[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        Solution solution = new Solution();
        int lengthOfLIS = solution.lengthOfLIS(nums);
        System.out.println(lengthOfLIS);
    }
}

复杂度分析：

• 时间复杂度：𝑂(𝑁2)。

• 空间复杂度：𝑂(𝑁)。

这道题还有一个时间复杂度为 𝑂(𝑁log𝑁)的解法，如下。

方法二：贪心算法（二分法）

思路：每一次来一个新的数 num ，在 tail 数组（ tail 数组的定义在下面的示意图中有）中找大于等于 num 的那个数，试图让它变小， 以致于新来的数有更多的可能性接在它后面，成为一个更长的“上升子序列” ，这是“贪心算法”的思想。

在 tail 数组中找大于等于 num 的那个数，可以使用“二分法”

Python 代码：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        size = len(nums)
        if size 2:
            return size

        tail = []
        for num in nums:
            # 找到大于等于 num 的第 1 个数
            l = 0
            r = len(tail)
            while l                 mid = l + (r - l) // 2
                if tail[mid]                     l = mid + 1
                else:
                    r = mid 
            if l == len(tail):
                tail.append(num)
            else:
                tail[l] = num
        return len(tail)

Java 代码：

public class Solution {

    public