最长上升子序列（LIS）算法详解：从O(n²)到O(n log n)的优化与路径记录

1. 项目背景与问题拆解：从“游园安排”到最长上升子序列

看到“游园安排”这个标题，很多参加过算法竞赛的朋友可能会心一笑。这其实是蓝桥杯2020年国赛的一道经典题目，它表面上是一个关于游园路线规划的故事，但内核却是一个经典的动态规划问题——最长上升子序列（Longest Increasing Subsequence, LIS）。题目通常会给你一个字符串序列，代表游客的姓名（或某种标识），你需要从中找出一个最长的、按字典序严格递增的子序列。这里的“递增”不是数值大小，而是字符串在字典序上的先后关系。

为什么这道题值得拿出来单独讲？因为在算法竞赛和面试中，LIS问题及其变种出现的频率极高。它不仅是动态规划的入门必修课，更是检验选手是否真正理解状态定义与转移的“试金石”。很多初学者能背出O(n²)的模板，但一旦遇到像“游园安排”这样需要输出具体方案、且元素是字符串的变种，就很容易卡壳。更不用说，在数据量大的情况下，如何将复杂度优化到O(n log n)并同时记录路径，这其中的技巧和细节，正是区分普通选手和高手的关键。

我自己在准备比赛和后来带学生刷题的过程中，发现大家在这类问题上的主要困惑点有几个：第一，如何将抽象的“安排”问题准确建模成LIS；第二，在优化到O(n log n)的贪心+二分算法中，如何记录下最终的子序列，而不仅仅是长度；第三，当存在多个合法的最长序列时，如何按题目要求输出字典序最小的那个。接下来，我就结合“游园安排”这道题，把LIS问题的“里子”和“面子”都掰开揉碎了讲清楚，让你不仅会做这一道题，更能掌握解决一大类问题的思路。

2. 问题建模：如何将游园名单转化为LIS模型

首先，我们得把题目描述“翻译”成算法语言。假设题目输入是一个字符串数组names，例如["Wo", "Aken", "Mike", "Anna", "Bob"]。我们需要找到一个最长的子序列，使得这个子序列中的字符串严格按照字典序递增排列。注意，是子序列，不是子串。这意味着我们可以跳过中间的一些人，只要保留下来的顺序是原顺序，且字典序递增即可。

例如，对于上面的数组，一个合法的递增子序列是["Aken", "Bob"]，但更长的可能是["Aken", "Anna", "Bob"]吗？不对，因为 “Anna” 和 “Bob” 在原数组中的顺序是Anna在Bob之前，但字典序上"Anna" < "Bob"是成立的，所以["Aken", "Anna", "Bob"]是一个长度为3的合法子序列。我们需要找到的就是最长的那个。

这直接对应了最长上升子序列（LIS）的定义：在一个序列中，找到一个最长的子序列，使得这个子序列的元素单调递增。只不过在经典LIS中，元素通常是数字，比较规则是数值大小；而在这里，元素是字符串，比较规则是字典序。字符串的字典序比较在编程语言中（如C++的string， Java的String.compareTo， Python的<）是直接支持的，因此模型转换非常直接。

所以，问题的核心模型就是：给定一个序列（字符串数组），求其字典序意义下的最长上升子序列的长度，并且需要输出这个子序列本身。当有多个方案时，输出字典序最小的方案。这里“字典序最小”指的是，在所有可能的最长上升子序列中，将它们视为一个字符串序列，从头开始比较，第一个出现不同字符的位置，字符较小的那个序列被视为更小。这个要求增加了问题的复杂度，因为我们需要在记录方案时进行额外的比较和选择。

3. 算法核心：从O(n²)动态规划到方案记录

我们先从最直观的动态规划解法开始，这是理解问题本质的基础。定义dp[i]表示以第i个字符串（names[i]）作为结尾的最长上升子序列的长度。状态转移方程很容易想到：dp[i] = max(dp[j]) + 1，其中0 <= j < i，且names[j] < names[i]（字典序小于）。 也就是说，对于每个位置i，我们看看它前面有哪些位置j的字符串比它小，然后从那些位置中，选一个dp[j]值最大的，接在后面，就形成了以i结尾的更长的子序列。

这个算法的时间复杂度是 O(n²)，对于n在 10^3 数量级的数据是可行的。但蓝桥杯的国赛题，数据规模往往会卡这个复杂度，要求我们使用 O(n log n) 的优化算法。不过，O(n²) 的DP有一个巨大的优点：非常容易记录具体方案。我们只需要在更新dp[i]的同时，用一个pre[i]数组记录下是从哪个j转移过来的（即names[i]的前驱节点）。最后，我们找到dp值最大的位置pos，然后通过pre数组向前回溯，就能还原出整个子序列。

这里就遇到了第一个关键细节：当有多个j都能使dp[i]达到最大值时，我们选择哪一个作为前驱？这直接影响了最终回溯得到的序列的字典序。题目要求输出字典序最小的最长子序列。一个常见的错误思路是：在转移时，如果dp[j] + 1 == dp[i]，并且names[j]的字典序比当前记录的前驱pre[i]对应的字符串更小，就更新pre[i] = j。然而，这个策略是错误的。

为什么？因为字典序的比较是全局的、逐位比较的。仅仅让每个位置i选择它前面字典序最小的前驱，并不能保证最终整个序列的字典序最小。考虑这个例子：序列[“b”, “a”, “c”]。最长上升子序列长度是2，有两个：[“b”, “c”]和[“a”, “c”]。字典序最小的是[“a”, “c”]。如果按照上述“局部最小”策略，对于“c”，它的前驱可以是“b”或“a”，两者dp值都是1。因为“a”字典序小于“b”，所以pre[“c”]会选择“a”。这看起来是对的。但如果我们把序列加长：[“b”, “a”, “d”, “c”]。最长上升子序列长度还是2，有多个。现在对于“d”，它的前驱“b”和“a”的dp值都是1，它会选择“a”。对于“c”，它前面比它小的有“b”,“a”，“d”（“d”比“c”大，不考虑）。“b”和“a”的dp值都是1，“c”也会选择“a”作为前驱。那么以“c”结尾的序列就是[“a”, “c”]。但这是全局最小的吗？不一定，因为以“d”结尾的序列[“a”, “d”]字典序可能比[“a”, “c”]更小（“c”和“d”比较）。实际上，我们需要在所有dp值最大的位置中，比较以它们结尾的整个序列的字典序。

因此，在 O(n²) DP 中，一个可靠的做法是：先完整计算出所有dp[i]和pre[i]（当多个j的dp[j]相同时，可以任意选一个，比如第一个遇到的j，因为后续我们会统一比较）。然后，我们找到所有dp值等于最大长度maxLen的位置，这些位置是潜在的终点。对于每一个这样的终点，我们通过pre链回溯，构造出完整的序列。最后，在所有构造出的序列中，选择字典序最小的那个输出。这个方法逻辑清晰，但构造和比较序列的过程在 n 较大时会比较耗时，不过对于 O(n²) 算法而言，这通常仍在可接受范围内。

注意：在回溯构造序列时，由于我们是从终点倒推到起点，得到的序列是逆序的，需要反转一下才能得到正序。

4. 优化算法：O(n log n)的贪心二分与路径记录

O(n²) 的算法在 n 超过 10^4 时就力不从心了。标准的 LIS 优化算法是贪心+二分，可以将时间复杂度降至 O(n log n)。这个算法的核心思想是：维护一个数组d，d[len]表示长度为len的上升子序列的末尾元素的最小可能值。注意，d本身并不是一个合法的 LIS，但它能帮助我们快速计算最大长度。

算法流程如下：

1. 初始化d为空，长度len = 0。
2. 遍历原序列的每个元素names[i]： a. 如果names[i]大于d的最后一个元素（即大于所有长度为len的序列的末尾），那么它可以接在后面，形成更长的序列。d[++len] = names[i]。 b. 否则，在d数组中找到第一个大于等于names[i]的位置pos，并用names[i]替换掉d[pos]。这个查找过程用二分法完成。

这个算法妙就妙在，它通过维护“末尾最小”这个贪心策略，保证了d数组是单调递增的（这允许我们使用二分查找），并且d的长度len就是最终 LIS 的长度。但它有一个“致命”的缺点：d数组最终存储的并不是一个真实的 LIS！我们无法直接从d数组回溯出原序列。例如，序列[2, 5, 3, 4]，d数组的最终状态是[2, 3, 4]，长度是3，但d本身[2,3,4]在原序列中的下标顺序并不是递增的（3在5后面）。

那么，如何在 O(n log n) 的算法中记录路径呢？这就需要我们引入另一个辅助数组pos。具体做法是：

• 我们不仅维护d数组，还维护一个等长的pos数组。pos[len]记录的是：当d[len]被更新为某个值时，这个值在原序列中的下标i。
• 同时，我们还需要一个pre数组（长度等于原序列 n），pre[i]记录的是：在以names[i]结尾的当前最优子序列中，names[i]的前一个元素在原序列中的下标。

更新逻辑如下：

1. 遍历到names[i]。
2. 在d数组中进行二分查找，找到第一个大于等于names[i]的位置p。
3. 更新d[p] = names[i]，同时更新pos[p] = i。这表示长度为p的子序列，其末尾最小元素更新为names[i]，且这个元素在原序列的位置是i。
4. 关键一步：记录前驱。names[i]的前驱，就是构成长度为p-1的子序列的末尾元素。这个末尾元素的下标记录在pos[p-1]里。所以，我们令pre[i] = pos[p-1]。注意，当p == 1时，表示这是长度为1的子序列，没有前驱，我们可以设pre[i] = -1。

通过这种方式，我们为原序列中的每个元素i，都记录了它在“当前已知的、以它结尾的最长上升子序列”中的前驱。当算法结束后，d的长度len就是 LIS 的长度。LIS 的最后一个元素的下标，就是pos[len]。然后我们就可以通过pre数组，从这个下标开始不断向前回溯，直到-1，从而得到整个 LIS 在原序列中的下标路径，进而得到字符串序列。

5. 处理字典序最小：比较策略的终极技巧

现在，我们有了在 O(n log n) 时间内记录路径的方法。但是，这记录的是“某一条”最长上升子序列的路径。当存在多条时，我们如何确保得到的是字典序最小的那一条呢？回顾一下d数组的定义：d[len]存储的是长度为 len 的上升子序列的末尾元素的最小可能值。这个“最小可能值”的贪心策略，本身就倾向于让序列的末尾尽可能小。但这对于保证整个序列的字典序最小，是充分条件吗？

并不是。d数组保证的是，对于每一个固定的长度，其末尾元素是可能达到的最小值。但这并不能直接推导出，由这些“最小末尾”连接起来的序列，其整体的字典序就是最小的。因为字典序是从头开始比较的，前面的字符权重更大。

这里就需要一个非常重要的洞察：为了得到字典序最小的最长上升子序列，我们应该从后往前构造它。或者说，在回溯的时候，如果我们有多个选择，我们应该选择能使前面部分字典序更小的那个选择。

具体到我们的算法中，当我们在d数组中用二分查找找到位置p时，我们执行的是d[p] = names[i]。如果有多个names[i]可以放在d[p]这个位置（即它们都等于当前的d[p]），按照标准的贪心算法，我们不会更新d[p]，因为值没有变小。但是，为了得到字典序更小的最终序列，当names[i]等于当前的d[p]时，我们也应该更新它！同时更新pos[p] = i和pre[i] = pos[p-1]。

为什么？考虑两个值相等的字符串，它们字典序相同。但是，它们在原序列中处于不同的位置。选择位置更靠后的那个作为d[p]，可能会为更长的子序列（p+1, p+2, ...）提供更多、更“小”的选择，从而可能影响到最终序列前面部分的选择。然而，这个策略需要仔细分析。实际上，一个更稳妥、更通用的方法是：我们不在更新d数组时做特殊处理，而是在最后回溯构造序列时，进行精细的比较和选择。

算法结束后，我们知道了最大长度len。LIS 的最后一个元素的下标是pos[len]。但pos[len]只记录了最后一个被更新到d[len]位置的那个元素的下标。如果历史上有多個元素都曾作为d[len]（即它们都曾作为某个长度为len的子序列的末尾），那么pos[len]只保存了最后一个。我们需要的是所有可能作为结尾的下标。

因此，我们需要改进记录方式。我们不再只用一个pos数组，而是用一个vector数组endsAt[len]，来记录所有能够形成长度为len的上升子序列的末尾元素的下标。在更新时：

• 如果names[i]大于d[len]，那么它可以形成长度为len+1的序列。d[++len] = names[i]，并将i加入到endsAt[len]中。pre[i]可以从endsAt[len-1]中任意一个下标转移过来（通常我们选最后一个，因为后续会比较）。
• 如果names[i]需要替换d[p]，那么d[p] = names[i]，并且将i加入到endsAt[p]中。同样，pre[i]从endsAt[p-1]中获取。

最终，我们得到endsAt[len]，里面是所有可能作为最长子序列末尾的下标。我们的目标是：从endsAt[len]中选一个下标开始回溯，使得回溯得到的整个序列的字典序最小。

如何比较？暴力方法是，对endsAt[len]中的每个下标，都回溯出一个序列，然后比较这些序列的字典序。但这样最坏情况是 O(n²) 的。我们可以用动态规划的思想，从后往前递推每个位置的“最佳后继”。

定义bestFrom[i]表示：从下标i开始（即以names[i]作为序列的第一个元素），能够构成的最长上升子序列是什么（用字符串序列表示）。但这个状态空间太大。一个巧妙的做法是：我们知道了最大长度len，那么对于长度为k的子序列，我们总是希望它的第一个元素尽可能小（因为字典序是从头比较的）。

因此，我们可以从k = len递减到k = 1来构造序列：

1. 设currentLen = len。
2. 在endsAt[currentLen]中，选择对应字符串字典序最小的那个下标i，作为我们序列中第currentLen个元素（从后往前看是第一个）。
3. 然后，我们需要找到第currentLen-1个元素。它应该在endsAt[currentLen-1]中，并且满足两个条件：a) 它的下标j必须小于我们刚选的i（因为子序列要保序）；b)names[j] < names[i]（因为要严格递增）。
4. 在满足条件的j中，我们再次选择names[j]字典序最小的那个。
5. 重复步骤3-4，直到currentLen变为0。

这个算法在每一步都选择当前条件下字典序最小的元素，从而保证了最终序列的字典序最小。实现时，我们可以对每个endsAt[k]按下标排序，然后用二分查找快速找到满足j < i且names[j] < names[i]的候选者中，字典序最小的那个。由于k从len递减到1，且每个endsAt[k]的大小总和是 O(n) 的，整体复杂度可以控制在 O(n log n)。

6. 代码实现与细节剖析

理论讲完了，我们来看具体代码实现。这里我用 C++ 给出一个清晰且带有详细注释的版本，它实现了 O(n log n) 的贪心二分算法，并妥善处理了路径记录和字典序最小的问题。选择 C++ 是因为其在算法竞赛中的高效和普遍性，但思路完全适用于其他语言。

#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; int main() { string s; cin >> s; // 假设输入是一个长字符串，名字之间没有空格，需要分割 // 题目通常名字是连续大写字母开头，我们可以根据大写字母来分割 // 这里简化处理，假设输入已经是空格分隔的名字字符串，或者我们手动分割。 // 例如：输入 "Wo Aken Mike Anna Bob" vector<string> names; // 分割字符串的代码（根据具体输入格式调整） // 这里假设用空格分割 size_t pos = 0; while ((pos = s.find(' ')) != string::npos) { names.push_back(s.substr(0, pos)); s.erase(0, pos + 1); } if (!s.empty()) names.push_back(s); int n = names.size(); if (n == 0) { cout << endl; return 0; } // d[len] 表示长度为len的LIS的末尾字符串的最小值 vector<string> d(n + 1); // pos[len] 记录d[len]对应的原序列下标（这里我们只记录最后一个，简化版） // 为了处理字典序最小，我们需要更复杂的记录，这里先给出简化版（可能得不到字典序最小） vector<int> pos(n + 1, -1); // pre[i] 记录以names[i]结尾的LIS中，前一个元素的下标 vector<int> pre(n, -1); int len = 0; // 当前已知的LIS最大长度 for (int i = 0; i < n; ++i) { // 二分查找第一个 >= names[i] 的位置 int l = 1, r = len, p = len + 1; // p初始化为len+1，表示需要扩展 while (l <= r) { int mid = (l + r) / 2; if (d[mid] >= names[i]) { // 注意：这里是 >=，为了替换第一个>=的 p = mid; r = mid - 1; } else { l = mid + 1; } } // 更新d和pos d[p] = names[i]; pos[p] = i; // 记录前驱 if (p > 1) { pre[i] = pos[p - 1]; } else { pre[i] = -1; } if (p > len) { len = p; } } // 此时len就是最大长度 // 但上面的简化版pos只记录了最后一个，要得到字典序最小，需要从所有可能的结尾中选 // 我们需要找到所有dp值等于len的i（这里dp[i]可以通过另一种方式记录，或者重构） // 重构dp值：我们可以再跑一遍，或者利用pre和len倒推。 // 更健壮的方法是：维护一个dp数组，dp[i]表示以i结尾的LIS长度 // 我们在二分查找时，p就是以names[i]结尾的LIS长度 vector<int> dp(n); // 重新初始化d和pos，同时记录dp d.assign(n + 1, ""); len = 0; for (int i = 0; i < n; ++i) { int l = 1, r = len, p = 1; while (l <= r) { int mid = (l + r) / 2; if (d[mid] >= names[i]) { r = mid - 1; } else { p = mid + 1; l = mid + 1; } } // 另一种二分写法，找到第一个>=的，或者最后一个<的+1 // 这里我们采用另一种常见写法： p = lower_bound(d.begin() + 1, d.begin() + len + 1, names[i]) - d.begin(); d[p] = names[i]; dp[i] = p; if (p > len) len = p; } // 现在dp[i]存储了以i结尾的LIS长度 // 找出所有dp[i] == len的i vector<int> candidates; for (int i = 0; i < n; ++i) { if (dp[i] == len) { candidates.push_back(i); } } // 从candidates中构造序列，并选择字典序最小的 // 由于要字典序最小，我们需要从后往前构造，并每次选择当前合法的、字典序最小的字符串 vector<string> ans(len); int currentIndex = -1; int currentLen = len; // 从最后一位开始选 for (int k = len; k >= 1; --k) { // 在所有dp[i] == k 的i中，选择names[i]字典序最小的，并且要满足： // 如果已经选了后面的元素currentIndex，则这个i必须 < currentIndex 且 names[i] < names[currentIndex] string minStr = "{"; // ASCII中'{'比所有字母都大，用作初始最大值 int chosen = -1; for (int i : candidates) { if (dp[i] != k) continue; if (currentIndex != -1) { if (i >= currentIndex || names[i] >= names[currentIndex]) continue; } if (names[i] < minStr) { minStr = names[i]; chosen = i; } } // 找到当前位的最佳选择 ans[k - 1] = minStr; currentIndex = chosen; // 下一轮，候选者范围可以缩小为所有下标小于chosen且dp值为k-1的 // 这里我们简单地将candidates更新为所有满足条件的i，实际可以优化 vector<int> newCandidates; for (int i = 0; i < n; ++i) { if (dp[i] == k - 1 && i < currentIndex && names[i] < names[currentIndex]) { newCandidates.push_back(i); } } candidates = std::move(newCandidates); } // 输出结果 for (int i = 0; i < len; ++i) { cout << ans[i]; if (i != len - 1) cout << " "; } cout << endl; return 0; }

这段代码是一个相对清晰的实现，但其中关于字典序最小的处理部分（最后那个循环）在极端情况下可能不是最优的，但清晰地展示了思路。在实际竞赛中，为了效率，我们通常会采用更精巧的数据结构（如根据dp值和下标构建二维结构，并排序）来加速查找过程。但核心思想不变：从后往前，在满足递增关系和顺序关系的约束下，每一步都贪心地选择字典序最小的字符串。

7. 常见踩坑点与调试心得

即使理解了算法，实现时也难免踩坑。这里分享几个我在这道题以及类似LIS问题中总结的常见陷阱：

1. 二分查找的边界与条件：这是最容易出错的地方。在贪心二分算法中，我们是要找第一个大于等于names[i]的位置（对于严格递增LIS）。如果写成找第一个大于的位置，对于连续相等的字符串，算法可能就无法正确更新，导致长度计算错误。lower_bound函数就是干这个的。如果自己手写二分，务必注意循环条件和更新逻辑。一个简单的测试：输入序列[“a”, “a”, “a”]，最长严格递增子序列长度应该是1。如果你的算法输出3，那肯定是比较条件写错了（应该是>=而不是>）。

2. 字典序比较与字符串相等：题目要求“严格递增”，这意味着names[i]必须小于names[j]，不能等于。在比较时，直接使用<运算符即可。但要注意，在记录路径选择前驱时，如果遇到字典序相等的字符串，它们不能接在彼此后面（因为不满足严格递增），但它们可以作为不同位置的候选。在最后构造字典序最小序列时，相等字符串的选择会影响结果，因为它们在原序列中的位置不同。

3. 路径回溯时的下标与值混淆：pre[i]记录的是前驱的下标，不是字符串本身。在回溯时，我们是从一个下标i通过pre[i]跳到上一个下标j。最终得到的是一串下标，需要再映射回names数组才能得到字符串序列。务必保持清醒，不要混用。

4. 多方案字典序最小的处理时机：正如前面所讨论的，在 O(n log n) 算法中，简单地用pre数组记录前驱，最后从pos[len]回溯，得到的可能不是字典序最小的。必须在得到所有可能的终点（dp[i]==len的 i）后，进行全局的比较和选择。一个常见的简化方法是：在更新d[p]时，如果names[i]等于当前的d[p]，我们也进行更新（即用i替换pos[p]）。这个策略基于一个假设：对于相同的末尾值，选择更靠后的位置，可能在构造更前面的部分时有更多选择，从而可能得到字典序更小的序列。这个假设在大多数情况下是成立的，并且能通过蓝桥杯的评测数据，但它并不是严格正确的。不过对于竞赛而言，这是一个行之有效的“启发式策略”，可以简化代码。如果追求绝对正确，就需要实现前面提到的从后往前贪心选择的完整逻辑。

5. 输入格式的解析：“游园安排”题目的输入往往是一个长字符串，所有名字连在一起，每个名字以大写字母开头。例如"WoAkenMikeAnnaBob"。你需要正确地分割出每个名字。分割逻辑要写对：遍历字符串，遇到大写字母，就开始一个新的名字，直到下一个大写字母之前。这是基础的字符串处理，但写错了会导致整个结果错误。建议单独写一个分割函数，并打印分割后的结果进行验证。

调试时，最好先用小规模、有代表性的数据测试。例如：

• 测试严格递增序列：[“A”, “B”, “C”, “D”]，结果应为本身。
• 测试严格递减序列：[“D”, “C”, “B”, “A”]，结果应为任意一个字符，长度为1。
• 测试有相等元素的序列：[“A”, “A”, “B”, “B”]，最长严格递增子序列应为[“A”, “B”]，长度为2。
• 测试字典序最小的选择：[“B”, “A”, “C”]，最长长度为2，有两个序列[“B”, “C”]和[“A”, “C”]，你的程序应输出[“A”, “C”]。
• 测试更复杂的序列：[“Wo”, “Aken”, “Mike”, “Anna”, “Bob”]，手动推导一下正确结果，然后和程序输出对比。

8. 举一反三：LIS变种问题与扩展思考

掌握了“游园安排”这道题，你基本上就掌握了LIS问题的核心。但算法竞赛的魅力就在于变化。这里列举几个常见的LIS变种，你可以用我们上面讨论的思路去尝试解决：

1. 最长不下降子序列（Longest Non-decreasing Subsequence）：这是将“严格递增”改为“非严格递增”（即允许相等）。在贪心二分算法中，只需要将二分查找的条件从“第一个大于等于”改为“第一个大于”即可。因为对于d数组，我们现在希望它维护的是“长度为 len 的不下降子序列的末尾元素的最小可能值”。当遇到一个等于当前末尾的元素时，它可以接在后面而不破坏“不下降”的性质，所以我们应该去更新第一个大于它的位置，而不是大于等于。

2. 二维偏序问题（如信封嵌套、俄罗斯套娃）：这类问题通常给出一组二元组(w, h)，要求找到一个序列，使得w和h都严格递增（或满足某种偏序关系）。一个经典的解法是：先对其中一个维度（如w）进行排序，然后在另一个维度（h）上找 LIS。但需要注意，当w相等时，为了避免误选，通常需要对h进行降序排序，然后再在h上找 LIS。这就将二维问题转化成了一维 LIS。

3. 输出所有最长上升子序列的个数：这需要结合动态规划计数。在 O(n²) 的DP中，可以定义cnt[i]为以i结尾的最长上升子序列的个数。在转移时，如果dp[j] + 1 > dp[i]，则更新dp[i]并重置cnt[i] = cnt[j]；如果dp[j] + 1 == dp[i]，则cnt[i] += cnt[j]。最后，将所有dp[i] == maxLen的cnt[i]累加。在 O(n log n) 的算法中，计数会变得复杂，需要维护d数组每个位置对应的方案数，涉及到去重，是一道不错的进阶练习题。

4. 带权值的LIS（最大上升子序列和）：每个元素有一个权值，求权值和最大的上升子序列。此时dp[i]的定义可以变为以i结尾的最大权值和。状态转移方程类似：dp[i] = max(dp[j]) + weight[i]，其中j < i且val[j] < val[i]。这通常只能用 O(n²) 的DP求解。如果数据范围大，可以考虑用数据结构（如树状数组、线段树）来优化前缀最大值查询，将复杂度降至 O(n log n)。

回到“游园安排”，它之所以经典，是因为它融合了 LIS 的长度求解、路径记录和多方案择优这三个核心难点。通过这道题，你应该建立起这样的思维模式：遇到序列上的最优子序列问题，先考虑是不是 LIS 的变种；如果需要输出方案，思考如何在状态转移时记录前驱；如果方案不唯一且有择优要求，分析择优的标准是全局的还是局部的，并设计相应的比较和选择策略。

最后，再强调一个工程实践中的技巧：在竞赛中，如果时间紧迫，对于“输出字典序最小方案”这类要求，如果想不到完美的 O(n log n) 解法，完全可以先实现一个正确但稍慢的 O(n²) DP 来求具体方案。在 n 不超过 5000 时，O(n²) 是完全可行的。先把分数拿到，再去思考优化。毕竟，正确的算法比高效的错误算法要好得多。