1. 项目概述从“游园安排”到算法竞赛的实战演练看到“第十一届蓝桥杯国赛——游园安排”这个标题很多参加过算法竞赛的朋友可能会心一笑。这可不是一份真实的公园游览计划而是一道经典的、极具代表性的动态规划问题。蓝桥杯作为国内覆盖面极广的软件和信息技术专业人才大赛其国赛题目往往融合了巧妙的算法思想与生动的现实场景包装。“游园安排”正是这样一道题它用一个看似生活化的“游园”故事考察了选手对最长上升子序列LIS这一核心算法的深刻理解与灵活应用能力。对于正在备赛的选手或是希望夯实动态规划基础的学习者来说深入剖析这道题其价值远超解出这一道题本身。它能帮你打通LIS问题的任督二脉理解如何将抽象问题转化为数学模型并掌握多种高效的求解策略。今天我们就来彻底拆解“游园安排”不仅告诉你“怎么做”更要说清楚“为什么这么做”以及在实际编码和竞赛中会遇到哪些坑。2. 问题核心与数学模型抽象2.1 题目场景还原与需求解析让我们先抛开代码回到题目描述的场景本身。通常这类题目的描述大致如下你拿到一份游园清单上面列出了N个必去的景点每个景点有一个唯一的“吸引力值”或“优先级”。但是游览路线有严格规定你必须按照清单给定的顺序依次决定是否游览每个景点且一旦游览后续游览的景点的吸引力值必须严格大于前一个游览的景点。你的目标是规划出一条尽可能长的游览序列即游览最多数量的景点并输出这个序列。核心需求拆解输入一个长度为N的序列数组代表景点的顺序和其“吸引力值”可能是字符串名称但本质可比较。约束选取一个子序列该子序列在原序列中的顺序不变子序列定义且其元素值严格单调递增。目标在所有满足约束的子序列中找到长度最长的那个。不仅要求出长度通常还要求输出这个具体的序列字典序最小或按原序输出。输出最长递增子序列本身。这几乎就是最长严格上升子序列Longest Increasing Subsequence, LIS问题的标准定义。理解这一点是解决所有衍生问题的基石。2.2 从场景到算法为什么是动态规划为什么这个问题天然适合用动态规划DP解决我们分析其是否具备DP的两个关键性质最优子结构假设我们已经知道以第i个景点结尾的最长上升子序列长度是dp[i]。那么要计算dp[i]我们可以遍历所有在i之前的景点j(0 j i)。如果attraction[j] attraction[i]那么景点i就可以接在以景点j结尾的上升子序列后面形成一个更长的序列此时dp[i] max(dp[i], dp[j] 1)。这说明大问题以i结尾的最长序列的最优解可以由小问题以j结尾的最长序列的最优解推导出来。重叠子问题在计算不同的dp[i]时我们会反复查询dp[0], dp[1], ..., dp[i-1]的值。如果采用递归暴力搜索这些值会被重复计算无数次。动态规划通过表格数组存储这些子问题的解避免了重复计算。因此我们自然可以定义出最基础的DP状态dp[i]表示以第i个元素景点结尾的最长严格上升子序列的长度。状态转移方程即为dp[i] max(dp[j]) 1其中j i且arr[j] arr[i]。注意这里有一个初学者极易混淆的点。dp[i]定义的是“以i结尾”的长度而不是“前i个元素中”的LIS长度。后者是一种不同的状态定义其转移会更复杂。在LIS问题中“以i结尾”的定义更直观也更容易追踪序列本身。3. 核心解法深度剖析从O(N²)到O(N log N)“游园安排”作为国赛题通常对数据规模有较高要求N可能达到10^5甚至更高。这意味着O(N²)的基础DP解法必然会超时。因此掌握更高效的算法是解决本题的关键。3.1 基础动态规划解法O(N²)理解本质尽管效率不高但O(N²)的DP是理解所有优化算法的基础。我们通过一个具体例子来演示。假设景点吸引力序列为arr [2, 5, 3, 4, 1, 7, 6]。初始化dp数组全初始化为1因为每个元素本身可以构成一个长度为1的上升子序列。dp [1, 1, 1, 1, 1, 1, 1]状态转移i0: 前面没有元素dp[0]保持1。i1 (arr[1]5): 看j0 (arr[0]2), 25所以dp[1] max(dp[1], dp[0]1) max(1, 2) 2。i2 (arr[2]3): 看j0 (23) -dp[2]2看j1 (53) 不满足上升跳过。最终dp[2]2。i3 (arr[3]4): j0 (24) - 可更新为2j1 (54)跳过j2 (34) -dp[3] max(2, dp[2]13) 3。... 依此类推。 最终dp [1, 2, 2, 3, 1, 4, 4]。最长上升子序列长度是max(dp) 4。如何输出序列我们需要额外一个pre数组记录路径。pre[i]存储在以arr[i]结尾的最长序列中arr[i]的前一个元素的下标。在更新dp[i]时如果发现通过j可以更新dp[i]就记录pre[i] j。最后从dp值最大的位置pos开始反向根据pre数组回溯即可得到序列。但需要注意这样得到的是“以某个位置结尾”的序列如果要求字典序最小的具体序列还需要一些额外处理。O(N²)解法的局限性其瓶颈在于对于每个i都要扫描所有前面的j。当N很大时10^5的平方是10^10远超普通计算机1秒内的运算能力约10^8次操作。3.2 贪心二分优化解法O(N log N)竞赛必备这是解决大规模LIS问题的标准算法也是“游园安排”这类题目期望的解法。它的核心思想非常巧妙我们并不关心最终序列中每个位置所有可能的选择我们只关心在相同长度下让序列的“末尾元素”尽可能小。这样可以为后续元素的添加留出更大空间。我们维护一个数组tail或者常命名为d。tail[len]表示长度为len的上升子序列中末尾元素的最小可能值。算法流程初始化tail为空数组。遍历原序列arr中的每个元素x a. 如果x大于tail中的所有元素即大于最后一个元素说明x可以接在当前最长的子序列后面形成更长的序列。将x追加到tail末尾。 b. 否则在tail数组中二分查找第一个大于等于x的元素的位置pos然后用x替换tail[pos]。这个操作的含义是对于长度为pos1的上升子序列我们现在找到了一个更小的末尾元素x这更有利于未来扩展。例子arr [2, 5, 3, 4, 1, 7, 6]x2:tail为空直接加入 -tail [2]x5: 大于tail末尾2追加 -tail [2, 5]x3: 二分查找tail中第一个3的是tail[1]5替换 -tail [2, 3]理解长度为2的LIS末尾元素最小可以变成3序列[2,3]比之前的[2,5]更好。x4: 大于末尾3追加 -tail [2, 3, 4]x1: 二分查找第一个1的是tail[0]2替换 -tail [1, 3, 4]理解长度为1的LIS末尾元素最小可以变成1。注意这并不代表LIS以1开头tail数组维护的是一种“可能性”。x7: 大于末尾4追加 -tail [1, 3, 4, 7]x6: 二分查找第一个6的是tail[3]7替换 -tail [1, 3, 4, 6]遍历结束tail的长度为4即LIS长度为4。但是请注意tail数组本身并不一定是真实的LIS例如这里的[1,3,4,6]在原序列中对应的子序列[1,3,4,6]并不存在原序列中1在4和6后面。tail数组只是一个“末端最小值的存档”。那么如何输出具体序列这是本题的另一个难点。我们需要在贪心二分的过程中额外记录信息。常见的方法是维护一个pos数组pos[i]表示原序列中第i个元素arr[i]在最终如果被选中它在LIS中可能处于的长度即它在tail数组中被放入的位置1。同时为了回溯我们还需要一个pre数组pre[i]记录在当前长度下arr[i]的前一个元素在原序列中的下标。这个前一个元素就是上一次tail在当前长度-1的位置上存储的值所对应的那个元素的下标。这个过程稍显复杂但原理是每当我们在tail[p]放入或替换元素x对应原序列下标i时我们就知道x有可能作为一个长度为p1的LIS的末尾。此时长度为p的LIS的末尾元素下标就是更新前tail[p-1]所对应的那个下标我们需要在更新tail[p]时同步记录其对应的原序列下标。这样在算法结束后我们从tail最后一个元素对应的原下标出发就能一步步向前回溯出整个序列。实操心得在竞赛中如果只要求长度那么只维护tail数组就足够了代码非常简洁。但如果要求输出具体序列建议在纸上完整模拟一遍上述过程并写出记录pos和pre的步骤理解其内在逻辑。这是区分选手是否真正掌握该算法的关键。4. 代码实现与细节处理下面我们给出“游园安排”问题的一个典型解法的代码框架假设输入是字符串序列景点名称需要输出字典序最小的最长上升子序列。import bisect def lis_sequence(arr): 返回给定序列 arr 的字典序最小的最长严格上升子序列。 arr: List[Comparable] 例如字符串列表。 n len(arr) if n 0: return [] # tail 数组存储长度为 (idx1) 的上升子序列的最小末尾元素 tail [] # tail_idx 存储 tail 中每个元素对应的原数组 arr 中的下标 tail_idx [] # pre 数组pre[i] 表示在以 arr[i] 结尾的LIS中arr[i]的前一个元素的下标 pre [-1] * n # pos 数组pos[i] 表示 arr[i] 如果作为结尾其LIS的长度从1开始计数 pos [0] * n for i, x in enumerate(arr): # 在 tail 中二分查找第一个 x 的位置 p bisect.bisect_left(tail, x) # 严格递增用 bisect_left # 如果是严格递增这里用 bisect_left 找到第一个 x 的 # 如果允许非严格递增即相等也算则用 bisect_right if p len(tail): # x 大于所有 tail 中的元素扩展 LIS tail.append(x) tail_idx.append(i) else: # 替换 tail 中的元素使其更小 tail[p] x tail_idx[p] i # 记录当前位置 i 对应的 LIS 长度 current_len p 1 pos[i] current_len # 记录前驱如果当前长度 1则前驱是上一个长度 tail[p-1] 对应的元素下标 if p 0: pre[i] tail_idx[p - 1] # 如果 p 0则 pre[i] 保持 -1表示这是长度为1的序列的开头 # 回溯构建序列 # 先找到 LIS 的最后一个元素的下标 lis_length len(tail) # 我们需要找到所有长度为 lis_length 的结尾中字典序最小的那个开始回溯 # 因为 tail 数组只保证了末尾最小但回溯时我们要保证整个序列字典序最小。 # 更稳妥的方法是从后往前扫描 arr 和 pos找到第一个 pos[i] lis_length 的 i。 # 但题目若要求字典序最小通常需要更细致的比较可能存在多个位置 pos[i]lis_length # 我们需要选择 arr[i] 最小的如果 arr[i] 相同则选择 i 靠后的因为回溯是从后往前。 # 这里简化我们取 tail 中最后一个元素对应的下标它对应一个可能的结尾 if lis_length 0: return [] # 更健壮的回溯方法收集所有可能结尾再按规则选 candidates [] for i in range(n-1, -1, -1): if pos[i] lis_length: candidates.append(i) # 按题目要求选择这里假设选第一个找到的从后往前 current candidates[0] if candidates else tail_idx[-1] # 回溯路径 path [] while current ! -1: path.append(arr[current]) current pre[current] # 路径是逆序的需要反转 return path[::-1] # 示例用法 if __name__ __main__: # 假设输入是字符串比较规则就是字符串的字典序 attractions [Welcome, Garden, Fountain, Castle, Zoo, Aquarium, Museum] result lis_sequence(attractions) print(最长游览序列字典序最小:, result) print(游览景点数:, len(result))关键细节解读二分查找的选择bisect_left用于严格递增因为它找到的是第一个大于等于x的位置用x替换它保证了tail数组严格递增。如果是非严格递增则应使用bisect_right。字典序最小输出上述代码的回溯部分做了简化。在严格意义上要保证输出的序列是所有最长序列中字典序最小的需要在回溯时进行选择。一个通用的策略是在知道LIS长度L后从原序列末尾向前扫描维护一个“当前可选的最小值”贪心地构建序列。具体步骤是初始化current 无穷小对于字符串可以是空字符串或特定最小字符remain L。从后往前遍历i如果pos[i] remain且arr[i] current对于严格递增LIS还需要满足arr[i]能接在后续已选序列的前面这通常意味着需要比较arr[i]和已选序列的第一个元素则选择arr[i]更新current arr[i],remain - 1。最后将选择的元素逆序输出。这种方法能确保字典序最小。空间复杂度O(N)用于存储pre,pos,tail,tail_idx等数组。5. 常见陷阱与实战调试技巧即便理解了算法在实战编码和调试中依然会碰到不少坑。以下是我在多次练习和比赛中总结出的经验5.1 严格递增 vs 非严格递增这是最致命的错误之一。题目描述是“严格大于”还是“可以等于”“游园安排”通常是严格递增。这直接决定了状态转移条件是arr[j] arr[i]还是arr[j] arr[i]。二分查找函数是bisect_left还是bisect_right。tail数组的性质是严格递增还是非递减。调试技巧首先用题目给的样例或自编的小样例包含相等元素测试。如果结果不对首先检查比较逻辑和二分查找函数。5.2 序列输出与字典序要求很多题目在求出长度后还要求输出序列本身并且可能是字典序最小的序列。tail数组优化法求出的只是长度以及一个可能的“末端最小”序列但这个序列在原数组中可能不连续甚至不存在。解决方案记录路径法如上文代码所示在贪心二分过程中通过pre和pos数组记录路径。这是最通用、最可靠的方法。反向贪心构造法在求出LIS长度L后从后往前扫描原数组和pos数组贪心地选取能构成最终序列且字典序最小的元素。这种方法思维难度稍高但代码可以更简洁且无需pre数组。实操心得在时间紧张的比赛中如果对输出序列的字典序有严格要求我建议直接采用“记录路径法”。虽然多用了O(N)的空间但逻辑清晰不易出错。在写出代码后务必用包含多个相同长度LIS的复杂样例进行测试例如序列[1, 3, 2, 4]最长上升子序列有[1,3,4]和[1,2,4]检查你的程序输出的是否是字典序最小的那个[1,2,4]。5.3 数据范围与性能边界O(N²) DP仅适用于 N 5000 左右在蓝桥杯国赛环境中通常不足以应对全部数据。O(N log N) 贪心二分可以轻松处理 N 10^5 甚至 10^6。元素类型如果景点名称是字符串比较操作 (,) 的时间复杂度是 O(L)其中L是字符串长度。在极端情况下字符串很长且N很大这可能成为性能瓶颈。但通常竞赛题中会保证字符串比较的总开销在可接受范围内。5.4 初始化与边界条件dp数组初始化为1。tail数组初始为空。pre数组初始化为-1表示无前驱。当输入序列为空时需要特判输出0或空列表。6. 问题变形与拓展思考掌握了标准的LIS解法“游园安排”这类题目就可以举一反三。算法竞赛中常见的变体有最长不下降子序列Non-decreasing将条件从“严格大于”改为“大于等于”只需将代码中的比较符和二分查找函数 (bisect_left改为bisect_right) 调整即可。二维LIS例如“信封嵌套”问题LeetCode 354。每个元素有长和宽两个属性要求找到一个序列使得长和宽都严格递增。解法是先对一维排序例如按宽度升序宽度相同时按高度降序然后在高度维度上求LIS。排序的目的在于将二维问题降为一维。带权值的LIS每个元素有一个权值求权值和最大的上升子序列。此时基础DP状态转移方程变为dp[i] max(dp[j] weight[i])其中j i且arr[j] arr[i]。优化时需要结合数据结构如树状数组、线段树来维护区间最大值将复杂度从O(N²)优化到O(N log N)。输出所有LIS要求输出所有可能的最长序列。这通常需要结合DFS回溯和DP复杂度较高一般数据范围较小。对于“游园安排”这道题将其吃透就意味着你掌握了动态规划中一个极其重要的模型。下次再遇到“最长递增子序列”这几个字你脑海中应该立刻浮现出tail数组和二分查找的形象。在竞赛中这往往是区分奖级的关键题之一。多练习几种变体理解其核心是“定义状态”和“优化转移”你就能在面对各种包装过的LIS问题时游刃有余。 最长上升子序列（LIS）算法精讲：从动态规划到贪心二分优化
1. 项目概述从“游园安排”到算法竞赛的实战演练看到“第十一届蓝桥杯国赛——游园安排”这个标题很多参加过算法竞赛的朋友可能会心一笑。这可不是一份真实的公园游览计划而是一道经典的、极具代表性的动态规划问题。蓝桥杯作为国内覆盖面极广的软件和信息技术专业人才大赛其国赛题目往往融合了巧妙的算法思想与生动的现实场景包装。“游园安排”正是这样一道题它用一个看似生活化的“游园”故事考察了选手对最长上升子序列LIS这一核心算法的深刻理解与灵活应用能力。对于正在备赛的选手或是希望夯实动态规划基础的学习者来说深入剖析这道题其价值远超解出这一道题本身。它能帮你打通LIS问题的任督二脉理解如何将抽象问题转化为数学模型并掌握多种高效的求解策略。今天我们就来彻底拆解“游园安排”不仅告诉你“怎么做”更要说清楚“为什么这么做”以及在实际编码和竞赛中会遇到哪些坑。2. 问题核心与数学模型抽象2.1 题目场景还原与需求解析让我们先抛开代码回到题目描述的场景本身。通常这类题目的描述大致如下你拿到一份游园清单上面列出了N个必去的景点每个景点有一个唯一的“吸引力值”或“优先级”。但是游览路线有严格规定你必须按照清单给定的顺序依次决定是否游览每个景点且一旦游览后续游览的景点的吸引力值必须严格大于前一个游览的景点。你的目标是规划出一条尽可能长的游览序列即游览最多数量的景点并输出这个序列。核心需求拆解输入一个长度为N的序列数组代表景点的顺序和其“吸引力值”可能是字符串名称但本质可比较。约束选取一个子序列该子序列在原序列中的顺序不变子序列定义且其元素值严格单调递增。目标在所有满足约束的子序列中找到长度最长的那个。不仅要求出长度通常还要求输出这个具体的序列字典序最小或按原序输出。输出最长递增子序列本身。这几乎就是最长严格上升子序列Longest Increasing Subsequence, LIS问题的标准定义。理解这一点是解决所有衍生问题的基石。2.2 从场景到算法为什么是动态规划为什么这个问题天然适合用动态规划DP解决我们分析其是否具备DP的两个关键性质最优子结构假设我们已经知道以第i个景点结尾的最长上升子序列长度是dp[i]。那么要计算dp[i]我们可以遍历所有在i之前的景点j(0 j i)。如果attraction[j] attraction[i]那么景点i就可以接在以景点j结尾的上升子序列后面形成一个更长的序列此时dp[i] max(dp[i], dp[j] 1)。这说明大问题以i结尾的最长序列的最优解可以由小问题以j结尾的最长序列的最优解推导出来。重叠子问题在计算不同的dp[i]时我们会反复查询dp[0], dp[1], ..., dp[i-1]的值。如果采用递归暴力搜索这些值会被重复计算无数次。动态规划通过表格数组存储这些子问题的解避免了重复计算。因此我们自然可以定义出最基础的DP状态dp[i]表示以第i个元素景点结尾的最长严格上升子序列的长度。状态转移方程即为dp[i] max(dp[j]) 1其中j i且arr[j] arr[i]。注意这里有一个初学者极易混淆的点。dp[i]定义的是“以i结尾”的长度而不是“前i个元素中”的LIS长度。后者是一种不同的状态定义其转移会更复杂。在LIS问题中“以i结尾”的定义更直观也更容易追踪序列本身。3. 核心解法深度剖析从O(N²)到O(N log N)“游园安排”作为国赛题通常对数据规模有较高要求N可能达到10^5甚至更高。这意味着O(N²)的基础DP解法必然会超时。因此掌握更高效的算法是解决本题的关键。3.1 基础动态规划解法O(N²)理解本质尽管效率不高但O(N²)的DP是理解所有优化算法的基础。我们通过一个具体例子来演示。假设景点吸引力序列为arr [2, 5, 3, 4, 1, 7, 6]。初始化dp数组全初始化为1因为每个元素本身可以构成一个长度为1的上升子序列。dp [1, 1, 1, 1, 1, 1, 1]状态转移i0: 前面没有元素dp[0]保持1。i1 (arr[1]5): 看j0 (arr[0]2), 25所以dp[1] max(dp[1], dp[0]1) max(1, 2) 2。i2 (arr[2]3): 看j0 (23) -dp[2]2看j1 (53) 不满足上升跳过。最终dp[2]2。i3 (arr[3]4): j0 (24) - 可更新为2j1 (54)跳过j2 (34) -dp[3] max(2, dp[2]13) 3。... 依此类推。 最终dp [1, 2, 2, 3, 1, 4, 4]。最长上升子序列长度是max(dp) 4。如何输出序列我们需要额外一个pre数组记录路径。pre[i]存储在以arr[i]结尾的最长序列中arr[i]的前一个元素的下标。在更新dp[i]时如果发现通过j可以更新dp[i]就记录pre[i] j。最后从dp值最大的位置pos开始反向根据pre数组回溯即可得到序列。但需要注意这样得到的是“以某个位置结尾”的序列如果要求字典序最小的具体序列还需要一些额外处理。O(N²)解法的局限性其瓶颈在于对于每个i都要扫描所有前面的j。当N很大时10^5的平方是10^10远超普通计算机1秒内的运算能力约10^8次操作。3.2 贪心二分优化解法O(N log N)竞赛必备这是解决大规模LIS问题的标准算法也是“游园安排”这类题目期望的解法。它的核心思想非常巧妙我们并不关心最终序列中每个位置所有可能的选择我们只关心在相同长度下让序列的“末尾元素”尽可能小。这样可以为后续元素的添加留出更大空间。我们维护一个数组tail或者常命名为d。tail[len]表示长度为len的上升子序列中末尾元素的最小可能值。算法流程初始化tail为空数组。遍历原序列arr中的每个元素x a. 如果x大于tail中的所有元素即大于最后一个元素说明x可以接在当前最长的子序列后面形成更长的序列。将x追加到tail末尾。 b. 否则在tail数组中二分查找第一个大于等于x的元素的位置pos然后用x替换tail[pos]。这个操作的含义是对于长度为pos1的上升子序列我们现在找到了一个更小的末尾元素x这更有利于未来扩展。例子arr [2, 5, 3, 4, 1, 7, 6]x2:tail为空直接加入 -tail [2]x5: 大于tail末尾2追加 -tail [2, 5]x3: 二分查找tail中第一个3的是tail[1]5替换 -tail [2, 3]理解长度为2的LIS末尾元素最小可以变成3序列[2,3]比之前的[2,5]更好。x4: 大于末尾3追加 -tail [2, 3, 4]x1: 二分查找第一个1的是tail[0]2替换 -tail [1, 3, 4]理解长度为1的LIS末尾元素最小可以变成1。注意这并不代表LIS以1开头tail数组维护的是一种“可能性”。x7: 大于末尾4追加 -tail [1, 3, 4, 7]x6: 二分查找第一个6的是tail[3]7替换 -tail [1, 3, 4, 6]遍历结束tail的长度为4即LIS长度为4。但是请注意tail数组本身并不一定是真实的LIS例如这里的[1,3,4,6]在原序列中对应的子序列[1,3,4,6]并不存在原序列中1在4和6后面。tail数组只是一个“末端最小值的存档”。那么如何输出具体序列这是本题的另一个难点。我们需要在贪心二分的过程中额外记录信息。常见的方法是维护一个pos数组pos[i]表示原序列中第i个元素arr[i]在最终如果被选中它在LIS中可能处于的长度即它在tail数组中被放入的位置1。同时为了回溯我们还需要一个pre数组pre[i]记录在当前长度下arr[i]的前一个元素在原序列中的下标。这个前一个元素就是上一次tail在当前长度-1的位置上存储的值所对应的那个元素的下标。这个过程稍显复杂但原理是每当我们在tail[p]放入或替换元素x对应原序列下标i时我们就知道x有可能作为一个长度为p1的LIS的末尾。此时长度为p的LIS的末尾元素下标就是更新前tail[p-1]所对应的那个下标我们需要在更新tail[p]时同步记录其对应的原序列下标。这样在算法结束后我们从tail最后一个元素对应的原下标出发就能一步步向前回溯出整个序列。实操心得在竞赛中如果只要求长度那么只维护tail数组就足够了代码非常简洁。但如果要求输出具体序列建议在纸上完整模拟一遍上述过程并写出记录pos和pre的步骤理解其内在逻辑。这是区分选手是否真正掌握该算法的关键。4. 代码实现与细节处理下面我们给出“游园安排”问题的一个典型解法的代码框架假设输入是字符串序列景点名称需要输出字典序最小的最长上升子序列。import bisect def lis_sequence(arr): 返回给定序列 arr 的字典序最小的最长严格上升子序列。 arr: List[Comparable] 例如字符串列表。 n len(arr) if n 0: return [] # tail 数组存储长度为 (idx1) 的上升子序列的最小末尾元素 tail [] # tail_idx 存储 tail 中每个元素对应的原数组 arr 中的下标 tail_idx [] # pre 数组pre[i] 表示在以 arr[i] 结尾的LIS中arr[i]的前一个元素的下标 pre [-1] * n # pos 数组pos[i] 表示 arr[i] 如果作为结尾其LIS的长度从1开始计数 pos [0] * n for i, x in enumerate(arr): # 在 tail 中二分查找第一个 x 的位置 p bisect.bisect_left(tail, x) # 严格递增用 bisect_left # 如果是严格递增这里用 bisect_left 找到第一个 x 的 # 如果允许非严格递增即相等也算则用 bisect_right if p len(tail): # x 大于所有 tail 中的元素扩展 LIS tail.append(x) tail_idx.append(i) else: # 替换 tail 中的元素使其更小 tail[p] x tail_idx[p] i # 记录当前位置 i 对应的 LIS 长度 current_len p 1 pos[i] current_len # 记录前驱如果当前长度 1则前驱是上一个长度 tail[p-1] 对应的元素下标 if p 0: pre[i] tail_idx[p - 1] # 如果 p 0则 pre[i] 保持 -1表示这是长度为1的序列的开头 # 回溯构建序列 # 先找到 LIS 的最后一个元素的下标 lis_length len(tail) # 我们需要找到所有长度为 lis_length 的结尾中字典序最小的那个开始回溯 # 因为 tail 数组只保证了末尾最小但回溯时我们要保证整个序列字典序最小。 # 更稳妥的方法是从后往前扫描 arr 和 pos找到第一个 pos[i] lis_length 的 i。 # 但题目若要求字典序最小通常需要更细致的比较可能存在多个位置 pos[i]lis_length # 我们需要选择 arr[i] 最小的如果 arr[i] 相同则选择 i 靠后的因为回溯是从后往前。 # 这里简化我们取 tail 中最后一个元素对应的下标它对应一个可能的结尾 if lis_length 0: return [] # 更健壮的回溯方法收集所有可能结尾再按规则选 candidates [] for i in range(n-1, -1, -1): if pos[i] lis_length: candidates.append(i) # 按题目要求选择这里假设选第一个找到的从后往前 current candidates[0] if candidates else tail_idx[-1] # 回溯路径 path [] while current ! -1: path.append(arr[current]) current pre[current] # 路径是逆序的需要反转 return path[::-1] # 示例用法 if __name__ __main__: # 假设输入是字符串比较规则就是字符串的字典序 attractions [Welcome, Garden, Fountain, Castle, Zoo, Aquarium, Museum] result lis_sequence(attractions) print(最长游览序列字典序最小:, result) print(游览景点数:, len(result))关键细节解读二分查找的选择bisect_left用于严格递增因为它找到的是第一个大于等于x的位置用x替换它保证了tail数组严格递增。如果是非严格递增则应使用bisect_right。字典序最小输出上述代码的回溯部分做了简化。在严格意义上要保证输出的序列是所有最长序列中字典序最小的需要在回溯时进行选择。一个通用的策略是在知道LIS长度L后从原序列末尾向前扫描维护一个“当前可选的最小值”贪心地构建序列。具体步骤是初始化current 无穷小对于字符串可以是空字符串或特定最小字符remain L。从后往前遍历i如果pos[i] remain且arr[i] current对于严格递增LIS还需要满足arr[i]能接在后续已选序列的前面这通常意味着需要比较arr[i]和已选序列的第一个元素则选择arr[i]更新current arr[i],remain - 1。最后将选择的元素逆序输出。这种方法能确保字典序最小。空间复杂度O(N)用于存储pre,pos,tail,tail_idx等数组。5. 常见陷阱与实战调试技巧即便理解了算法在实战编码和调试中依然会碰到不少坑。以下是我在多次练习和比赛中总结出的经验5.1 严格递增 vs 非严格递增这是最致命的错误之一。题目描述是“严格大于”还是“可以等于”“游园安排”通常是严格递增。这直接决定了状态转移条件是arr[j] arr[i]还是arr[j] arr[i]。二分查找函数是bisect_left还是bisect_right。tail数组的性质是严格递增还是非递减。调试技巧首先用题目给的样例或自编的小样例包含相等元素测试。如果结果不对首先检查比较逻辑和二分查找函数。5.2 序列输出与字典序要求很多题目在求出长度后还要求输出序列本身并且可能是字典序最小的序列。tail数组优化法求出的只是长度以及一个可能的“末端最小”序列但这个序列在原数组中可能不连续甚至不存在。解决方案记录路径法如上文代码所示在贪心二分过程中通过pre和pos数组记录路径。这是最通用、最可靠的方法。反向贪心构造法在求出LIS长度L后从后往前扫描原数组和pos数组贪心地选取能构成最终序列且字典序最小的元素。这种方法思维难度稍高但代码可以更简洁且无需pre数组。实操心得在时间紧张的比赛中如果对输出序列的字典序有严格要求我建议直接采用“记录路径法”。虽然多用了O(N)的空间但逻辑清晰不易出错。在写出代码后务必用包含多个相同长度LIS的复杂样例进行测试例如序列[1, 3, 2, 4]最长上升子序列有[1,3,4]和[1,2,4]检查你的程序输出的是否是字典序最小的那个[1,2,4]。5.3 数据范围与性能边界O(N²) DP仅适用于 N 5000 左右在蓝桥杯国赛环境中通常不足以应对全部数据。O(N log N) 贪心二分可以轻松处理 N 10^5 甚至 10^6。元素类型如果景点名称是字符串比较操作 (,) 的时间复杂度是 O(L)其中L是字符串长度。在极端情况下字符串很长且N很大这可能成为性能瓶颈。但通常竞赛题中会保证字符串比较的总开销在可接受范围内。5.4 初始化与边界条件dp数组初始化为1。tail数组初始为空。pre数组初始化为-1表示无前驱。当输入序列为空时需要特判输出0或空列表。6. 问题变形与拓展思考掌握了标准的LIS解法“游园安排”这类题目就可以举一反三。算法竞赛中常见的变体有最长不下降子序列Non-decreasing将条件从“严格大于”改为“大于等于”只需将代码中的比较符和二分查找函数 (bisect_left改为bisect_right) 调整即可。二维LIS例如“信封嵌套”问题LeetCode 354。每个元素有长和宽两个属性要求找到一个序列使得长和宽都严格递增。解法是先对一维排序例如按宽度升序宽度相同时按高度降序然后在高度维度上求LIS。排序的目的在于将二维问题降为一维。带权值的LIS每个元素有一个权值求权值和最大的上升子序列。此时基础DP状态转移方程变为dp[i] max(dp[j] weight[i])其中j i且arr[j] arr[i]。优化时需要结合数据结构如树状数组、线段树来维护区间最大值将复杂度从O(N²)优化到O(N log N)。输出所有LIS要求输出所有可能的最长序列。这通常需要结合DFS回溯和DP复杂度较高一般数据范围较小。对于“游园安排”这道题将其吃透就意味着你掌握了动态规划中一个极其重要的模型。下次再遇到“最长递增子序列”这几个字你脑海中应该立刻浮现出tail数组和二分查找的形象。在竞赛中这往往是区分奖级的关键题之一。多练习几种变体理解其核心是“定义状态”和“优化转移”你就能在面对各种包装过的LIS问题时游刃有余。