49 | 面试题：最长上升子序列-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 49 | 面试题：最长上升子序列

在算法面试中，最长上升子序列（Longest Increasing Subsequence, LIS）是一道经典且富有挑战性的题目。它不仅考察了面试者对动态规划、二分查找等基础算法的理解，还检验了他们在面对复杂问题时将问题拆解、优化算法的能力。本章节将详细解析最长上升子序列的概念、解法，以及如何通过不同策略优化算法效率，帮助读者在面试中游刃有余地应对此类问题。

#### 一、问题定义

最长上升子序列问题可以描述为：给定一个无序的整数数组（nums），找到并返回数组中最长上升子序列的长度。注意，这里的子序列并不是子数组，它可以不连续，但必须保持相对顺序。例如，对于数组 `[10, 9, 2, 5, 3, 7, 101, 18]`，其最长上升子序列为 `[2, 3, 7, 101]`，长度为 4。

#### 二、解法概览

解决最长上升子序列问题主要有两种常用方法：动态规划（Dynamic Programming, DP）和二分查找优化（基于贪心+二分查找）。下面我们将分别介绍这两种方法。

##### 2.1 动态规划解法

**思路分析**：
动态规划是解决此类问题的直观方法。我们定义一个数组 `dp`，其中 `dp[i]` 表示以 `nums[i]` 结尾的最长上升子序列的长度。遍历数组 `nums`，对于每个元素 `nums[i]`，再向前遍历所有 `j < i` 的位置，如果 `nums[j] < nums[i]`，则说明 `nums[i]` 可以接在 `nums[j]` 后面形成一个更长的上升子序列。此时，我们更新 `dp[i]` 为 `dp[j] + 1` 和当前 `dp[i]` 中的较大值。最终，`dp` 数组中的最大值即为所求的最长上升子序列长度。

**代码实现**：

```python
def lengthOfLIS(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n  # 初始化dp数组，每个元素至少可以单独构成一个长度为1的子序列
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
```

**时间复杂度**：O(n^2)，其中 n 是数组的长度。由于有两层嵌套循环，所以时间复杂度为平方级别。

**空间复杂度**：O(n)，用于存储 dp 数组。

##### 2.2 二分查找优化解法

**思路分析**：
虽然动态规划能够解决问题，但在面对大数据量时，其性能可能成为瓶颈。一种更优的解法是利用贪心算法结合二分查找来优化。我们维护一个数组 `tails`，其中 `tails[i]` 表示长度为 `i+1` 的所有上升子序列中，末尾元素最小的那个子序列的末尾元素。遍历数组 `nums`，对于每个元素 `nums[i]`，我们使用二分查找在 `tails` 中找到第一个不小于 `nums[i]` 的位置 `pos`，如果 `pos` 等于 `tails` 的长度，说明找到了一个更长的上升子序列，直接添加到 `tails` 末尾；否则，更新 `tails[pos]` 为 `nums[i]`（保持子序列末尾元素尽可能小，以便后续可能的扩展）。

**代码实现**：

```python
def lengthOfLIS(nums):
    if not nums:
        return 0
    tails = []
    for num in nums:
        if not tails or num > tails[-1]:
            tails.append(num)
        else:
            left, right = 0, len(tails) - 1
            while left <= right:
                mid = (left + right) // 2
                if tails[mid] < num:
                    left = mid + 1
                else:
                    right = mid - 1
            tails[left] = num
    return len(tails)
```

**时间复杂度**：O(nlogn)，其中 n 是数组的长度。每个元素 `nums[i]` 最多被插入到 `tails` 数组一次，且每次插入都通过二分查找确定位置，因此时间复杂度为线性对数级别。

**空间复杂度**：O(n)，用于存储 `tails` 数组，其大小最多为 n（虽然实际大小通常远小于 n）。

#### 三、优化与变体

- **空间优化**：虽然二分查找优化解法已经相当高效，但如果对空间有极致要求，可以尝试使用其他数据结构（如平衡二叉搜索树）来替代数组，以在保持时间效率的同时减少空间占用。
- **变体问题**：最长上升子序列问题有很多变体，如求最长公共上升子序列（Longest Common Increasing Subsequence, LCIS）、最长不下降子序列（Longest Non-decreasing Subsequence, LNDS）等。这些问题虽然基本思路相似，但细节处理上有所不同，需要具体问题具体分析。
- **应用场景**：最长上升子序列问题不仅限于算法面试，还广泛应用于生物信息学、经济学等多个领域，如基因序列分析、股票价格预测等。

#### 四、总结

最长上升子序列问题是算法面试中的一道经典题目，通过动态规划和二分查找优化两种方法的介绍，我们不仅掌握了解决此类问题的基本技巧，还学习了如何在不同场景下选择合适的算法策略。在面试准备过程中，建议读者不仅要熟练掌握这两种解法，还要能够灵活应对问题的各种变体，以及理解其背后的算法思想和优化思路。

该分类下的相关小册推荐：

业务开发实用算法精讲

编程之道-算法面试(下)

数据结构与算法(下)

数据结构与算法(中)

数据结构与算法之美

数据结构与算法(上)

编程之道-算法面试(上)