在计算机科学与算法设计领域，序列处理问题占据着举足轻重的地位。其中，一个经典且具有广泛应用背景的问题便是“最长上升子序列”（Longest Increasing Subsequence，简称LIS）。它不仅仅是一个理论概念，更是解决诸多实际问题的重要工具。本文将围绕这一核心主题，从多个维度进行深入探讨，解答关于LIS的“是什么”、“为什么”、“如何”、“多少”、“哪里”以及“有哪些变种”等一系列普遍疑问。
何为最长上升子序列？
定义与构成
最长上升子序列，顾名思义，是从给定序列中提取出的一个子序列，使得该子序列的元素是严格单调递增的，并且其长度最长。
要理解LIS，首先需要明确“子序列”的概念。子序列是从原序列中删除零个或多个元素后，剩下的元素保持原相对顺序所构成的序列。例如，序列 [10, 22, 9, 33, 21, 50, 41, 60] 中，[10, 22, 33, 50, 60] 就是一个上升子序列，且其长度为5。而 [10, 33, 21] 则不是上升子序列，因为 33 > 21。
“上升”通常指“严格上升”，即后一个元素必须大于前一个元素。如果允许相等，则称为“最长非降子序列”。在大多数情况下，当提及LIS时，默认指的是严格上升。
一个示例
给定序列：
nums = [1, 3, 2, 4, 5]它的上升子序列可能有很多：
[1][3][1, 3][1, 2][1, 2, 4][1, 2, 4, 5][1, 3, 4][1, 3, 4, 5][2, 4, 5]- …
其中，最长的上升子序列是
[1, 2, 4, 5]或[1, 3, 4, 5]，它们的长度都是 4。因此，对于这个序列，最长上升子序列的长度是4。
为何要研究和求解最长上升子序列？
应用场景的广泛性
LIS问题并非空中楼阁，它在众多实际领域中都有着深刻的应用价值，为复杂问题的建模和求解提供了有效的范式。理解其背后原理，能够帮助我们更好地解决真实世界中的挑战。
-
数据分析与生物信息学
在基因序列比对、蛋白质结构分析等生物信息学领域，常常需要找到两条序列之间的相似性，这可以转化为寻找它们的最长公共子序列（LCS）。而LCS问题在某些特定情况下，可以通过对序列进行转换，简化为LIS问题来解决，例如通过构建一个二维点集，然后找到最长上升路径。
-
调度与资源分配
在任务调度、资源优化等场景中，例如有多个任务需要按顺序执行，每个任务都有其开始和结束时间。如果任务不能重叠，我们可能需要找到最长的任务链，这可以通过将任务抽象为点，然后应用LIS的思想来解决。
-
卡牌游戏与耐心排序
有一个名为“耐心排序”（Patience Sorting）的排序算法，其核心思想与LIS有着紧密联系。它模拟了纸牌游戏中的堆牌规则：牌必须放在比它小的牌上，或者创建一个新堆。最终堆的数量就是反序对的数量，而最长上升子序列的长度与此问题密切相关。
-
性能优化与数据压缩
在某些数据结构或算法设计中，通过识别数据中的单调模式，可以实现存储优化或计算加速。例如，在内存管理中，如果能识别出连续的、按大小排列的内存块，就能更高效地进行分配与回收。
如何求解最长上升子序列？
算法一：动态规划（O(N²) 时间复杂度）
这是最直观且易于理解的方法。其核心思想是，对于序列中的每一个元素，我们都尝试找出以它为结尾的最长上升子序列的长度。
-
定义状态：
设
dp[i]表示以第i个元素nums[i]结尾的最长上升子序列的长度。 -
状态转移方程：
要计算
dp[i]，我们需要遍历i之前的所有元素nums[j]（其中j < i）。如果nums[i] > nums[j]，则意味着nums[i]可以接在以nums[j]结尾的某个上升子序列后面，形成一个新的上升子序列。
因此，dp[i]的值将是所有满足nums[i] > nums[j]条件的(dp[j] + 1)中的最大值。
如果nums[i]不能接在任何一个上升子序列后面（即它比前面所有元素都小），那么它自身就构成一个长度为1的上升子序列。
所以，状态转移方程为：
dp[i] = 1 + max(dp[j])for allj < iandnums[j] < nums[i]。
如果不存在这样的j，则max(dp[j])视为 0。 -
初始化：
所有的
dp[i]初始值都为 1，因为每个元素自身都可以构成一个长度为 1 的上升子序列。 -
最终结果：
遍历完所有元素后，
dp数组中的最大值就是整个序列的最长上升子序列的长度。
示例演示（O(N²)）：
序列：
nums = [10, 9, 2, 5, 3, 7, 101, 18]初始化
dp = [1, 1, 1, 1, 1, 1, 1, 1](长度与 nums 相同)
i = 0, nums[0] = 10:
dp[0] = 1(初始值)i = 1, nums[1] = 9:
9不大于10，无j < 1且nums[j] < nums[1]。
dp[1] = 1i = 2, nums[2] = 2:
2不大于10或9。
dp[2] = 1i = 3, nums[3] = 5:考虑
j < 3:
nums[0]=10(5 < 10不行)
nums[1]=9(5 < 9不行)
nums[2]=2(5 > 2, 可以!dp[2]+1 = 1+1 = 2)
dp[3] = max(1, 2) = 2(最长上升子序列如[2, 5])i = 4, nums[4] = 3:考虑
j < 4:
nums[0]=10(3 < 10不行)
nums[1]=9(3 < 9不行)
nums[2]=2(3 > 2, 可以!dp[2]+1 = 1+1 = 2)
nums[3]=5(3 < 5不行)
dp[4] = max(1, 2) = 2(最长上升子序列如[2, 3])i = 5, nums[5] = 7:考虑
j < 5:
nums[2]=2(7 > 2,dp[2]+1 = 2)
nums[3]=5(7 > 5,dp[3]+1 = 3)
nums[4]=3(7 > 3,dp[4]+1 = 3)
dp[5] = max(1, 2, 3) = 3(最长上升子序列如[2, 5, 7]或[2, 3, 7])i = 6, nums[6] = 101:考虑
j < 6:
nums[0]=10(101 > 10,dp[0]+1 = 2)
nums[1]=9(101 > 9,dp[1]+1 = 2)
nums[2]=2(101 > 2,dp[2]+1 = 2)
nums[3]=5(101 > 5,dp[3]+1 = 3)
nums[4]=3(101 > 3,dp[4]+1 = 3)
nums[5]=7(101 > 7,dp[5]+1 = 4)
dp[6] = max(1, 2, 2, 2, 3, 3, 4) = 4(最长上升子序列如[2, 5, 7, 101])i = 7, nums[7] = 18:考虑
j < 7:
nums[0]=10(18 > 10,dp[0]+1 = 2)
nums[1]=9(18 > 9,dp[1]+1 = 2)
nums[2]=2(18 > 2,dp[2]+1 = 2)
nums[3]=5(18 > 5,dp[3]+1 = 3)
nums[4]=3(18 > 3,dp[4]+1 = 3)
nums[5]=7(18 > 7,dp[5]+1 = 4)
nums[6]=101(18 < 101不行)
dp[7] = max(1, 2, 2, 2, 3, 3, 4) = 4(最长上升子序列如[2, 5, 7, 18])最终
dp数组为[1, 1, 1, 2, 2, 3, 4, 4]。最大值为 4。
算法二：动态规划结合二分查找（O(N log N) 时间复杂度）
为了优化 O(N²) 的时间复杂度，我们可以利用一个巧妙的辅助数组 tails，并结合二分查找来达到 O(N log N) 的效率。
-
定义辅助数组
tails：tails[k]存储的是所有长度为k+1的上升子序列中，最小的那个结尾元素。
这个数组tails始终保持有序（因为我们总是用更小的元素替换相同长度的子序列的结尾）。
重要的是，tails数组的长度，就是当前找到的最长上升子序列的长度。但tails数组本身不构成任何一个具体的LIS。 -
遍历原始序列
nums：对于
nums中的每一个元素x：-
情况一：如果
x大于tails中所有的元素。这意味着
x可以接在当前最长的上升子序列后面，形成一个新的、更长的上升子序列。
此时，我们将x添加到tails数组的末尾。 -
情况二：如果
x不大于tails中所有的元素。这意味着
x不能直接扩展最长子序列。但x可能可以替换tails中的某个元素，从而为后续的元素提供一个更小的“结尾”，使得未来能够形成更长的上升子序列。
具体做法是：在tails数组中，找到第一个大于或等于x的元素。使用二分查找（lower_bound或等价操作）可以高效完成。
将找到的这个元素替换为x。这样做并不会改变tails数组的长度（即LIS的长度），但却可能优化了特定长度子序列的“结尾值”，使其更小，更有利于后续扩展。
-
情况一：如果
-
最终结果：
遍历结束后，
tails数组的长度就是最长上升子序列的长度。
示例演示（O(N log N)）：
序列：
nums = [10, 9, 2, 5, 3, 7, 101, 18]初始化
tails = []
x = 10:
tails为空，将10加入。tails = [10]x = 9:
9小于10。在tails中找到第一个>= 9的元素（即10），将其替换为9。
tails = [9]x = 2:
2小于9。在tails中找到第一个>= 2的元素（即9），将其替换为2。
tails = [2]x = 5:
5大于tails中所有元素（即2）。将5加入tails。
tails = [2, 5]x = 3:
3不大于5，但大于2。在tails中找到第一个>= 3的元素（即5），将其替换为3。
tails = [2, 3](注意：长度仍为2，但LIS结尾变成了更小的3)x = 7:
7大于tails中所有元素（即2, 3）。将7加入tails。
tails = [2, 3, 7]x = 101:
101大于tails中所有元素（即2, 3, 7）。将101加入tails。
tails = [2, 3, 7, 101]x = 18:
18不大于101，但大于7。在tails中找到第一个>= 18的元素（即101），将其替换为18。
tails = [2, 3, 7, 18](长度仍为4，结尾更小)最终
tails数组为[2, 3, 7, 18]。其长度为 4，即最长上升子序列的长度。
如何重构具体的上升子序列？
上述两种方法主要用于求解LIS的长度。如果需要获取具体的上升子序列，O(N²) 的动态规划方法更容易实现：
-
在计算
dp[i]时，额外维护一个predecessor[i]数组，记录nums[i]前一个接的元素nums[j]的索引j。 -
找到
dp数组中最大值对应的索引end_idx。 -
从
end_idx开始，沿着predecessor数组逆向回溯，即可得到一个具体的LIS。需要注意的是，可能存在多个LIS，这种方法只回溯其中一个。
对于 O(N log N) 的方法，重构LIS则相对复杂，通常需要存储更详细的历史信息，例如每个元素被放入 tails 数组时，它替换了哪个元素，以及它的前一个元素是谁。这通常涉及到更复杂的数据结构，如跳表或树，或者对原始序列进行预处理。
最长上升子序列有多少变体？
延伸与拓展
LIS问题是众多相关问题的基石，通过对其进行小幅修改，可以引申出许多有趣的变体：
-
最长非降子序列（Longest Non-decreasing Subsequence）：
允许子序列中的元素相等，即
nums[i] >= nums[j]。只需在 O(N²) DP 或 O(N log N) 二分查找中，将比较条件>改为>=即可。 -
最长下降子序列（Longest Decreasing Subsequence）：
元素严格单调递减。可以将原序列所有元素取负后求LIS，或者直接将比较条件
>改为<即可。 -
最长公共子序列（Longest Common Subsequence, LCS）：
虽然LCS通常用二维DP解决，但如果两个序列的元素都是唯一的，并且它们是某个全排列的子集，那么LCS可以通过将一个序列的元素映射到另一个序列的索引，然后求解LIS来简化。
-
最长上升子数组/子串（Longest Increasing Subarray/Substring）：
注意区分“子序列”和“子数组/子串”。子数组/子串要求元素在原序列中是连续的，这使得问题变得更简单，只需一次遍历即可。
-
最长比特onic子序列：
先单调递增，后单调递减的子序列。这可以分解为两次LIS问题，一次从左到右，一次从右到左，然后组合结果。
-
寻找第K个最长上升子序列：
这需要更高级的动态规划计数技巧，通常结合组合数学或图论中的路径计数方法，来统计并筛选出特定的LIS。
最长上升子序列在何处施展其威力？
更具体的应用剖析
除了前面提到的大方向，LIS在以下具体情境中亦有其独到之处：
-
货物装载优化：
假设有一批不同长度的木材，要将它们堆叠起来，要求下面的木材必须长于上面的木材。那么可以找到最长上升子序列，以确定最多能堆叠多少层。
-
体育赛事排名：
在某些多轮制的体育比赛中，选手得分会动态变化。如果需要找出哪些选手在整个比赛过程中，得分一直处于上升趋势且持续时间最长，这便是LIS的一个应用实例。
-
证券交易策略：
分析股票价格序列，找出价格连续上涨的最长周期，虽然这并非严格的LIS，但其变体可以帮助识别趋势。如果股价必须严格上涨才能被认为是“上升趋势链”，那么LIS模型就可以直接应用。
-
网络路由优化：
在某些特定网络拓扑中，数据包需要经过一系列节点，每个节点都有一个与其相关的性能指标（如延迟、带宽等）。如果要求数据包经过的节点性能指标单调递增（或递减），那么寻找最优路径可能涉及LIS问题。
最长上升子序列的规模与边界？
考量与约束
在实际问题中，对LIS的求解还会受到数据规模和元素特性的影响。
-
序列长度：
对于 O(N²) 的算法，当序列长度
N达到 10^3 到 10^4 时，计算时间可能变得不可接受（10^6 到 10^8 次操作）。而 O(N log N) 算法则能处理更大的N，例如 10^5 到 10^6 的序列长度（10^5 * log(10^5) 约为 1.7 * 10^6 次操作）。因此，对于大规模数据，O(N log N) 方法是首选。 -
元素取值范围：
LIS算法通常对元素的值本身没有特定限制，无论是整数、浮点数，只要能进行比较操作即可。如果元素是自定义对象，则需要定义一个有效的比较规则。
-
特殊序列：
-
完全升序序列：
[1, 2, 3, 4, 5]LIS长度为序列自身长度
N。 -
完全降序序列：
[5, 4, 3, 2, 1]LIS长度为 1（每个元素自身）。
-
所有元素相等：
[7, 7, 7, 7, 7]LIS长度为 1（严格上升要求）。如果是最长非降子序列，则为
N。 -
空序列：
LIS长度为 0。
-
完全升序序列：
总结
最长上升子序列是一个算法领域的基础且重要的问题。它不仅仅锻炼了我们对动态规划、二分查找等核心算法的掌握，更重要的是，它提供了一个强大的模型，能够被巧妙地应用于生物信息学、调度优化、数据分析等多个交叉学科和工程实践中。理解其各种求解方法及其变体，是提升算法思维能力和解决实际问题能力的有效途径。