算法竞赛入门：从蓝桥杯签到题看最长递增子序列（LIS）的三种解法

1. 项目概述：从一道“签到题”看算法竞赛的思维训练

“蓝桥杯”国赛的“签到题”，听起来是不是感觉手到擒来？很多刚接触算法竞赛的同学，看到“递增序列”这样的题目，再配上“签到题”的标签，可能第一反应是：“这不就是排个序或者简单遍历一下吗？”但如果你真这么想，可能就掉进了出题人精心设计的“思维陷阱”里。我参加过也带过不少算法竞赛，深知所谓的“签到题”往往不是考你会不会写代码，而是考你能否在短时间内，精准地理解题意、抽象模型，并选择最高效的解法。这道2019年国赛的“递增序列”题，就是一个绝佳的范例。它表面上问的是序列，内核却是在考察你对“单调性”和“子序列”概念的深刻理解，以及如何在有限的竞赛时间内，写出既正确又优雅的代码。这篇文章，我就带你彻底拆解这道题，不仅告诉你答案是什么，更重要的是分享我是如何一步步分析、推理，并最终形成解题思路的。无论你是正在备赛蓝桥杯的选手，还是想提升自己算法思维的程序员，相信这篇从实战角度出发的深度解析，都能让你有所收获。

2. 题目核心需求与模型抽象

2.1 题意解析：到底在问什么？

首先，我们必须抛开“签到题”的轻敌心态，严谨地审题。题目通常的描述是：给定一个长度为 N 的整数序列 A，我们需要找出其中最长的“递增序列”的长度。这里就出现了第一个关键点：“递增序列”在算法题中通常指“严格递增”还是“非严格递增”？

在大多数算法竞赛语境下，尤其是像蓝桥杯这样强调严谨性的比赛，“递增”往往默认为严格递增，即序列中后一个元素必须严格大于前一个元素（A[i] > A[i-1]）。如果是非严格递增（A[i] >= A[i-1]），题目通常会明确说明为“非递减序列”。这是我们构建逻辑的基础，一点都不能错。

接着是第二个关键点：这个“序列”是“连续”的还是“可以不连续”的？这是本题最核心的区分点，也是决定解题算法复杂度等级的分水岭。

• 连续递增子序列：要求在原序列中下标连续。例如序列[1, 3, 2, 4]，其连续递增子序列有[1, 3]（长度为2），[2, 4]（长度为2），最长的就是2。求解这个问题非常简单，只需要一次遍历，时间复杂度是 O(N)。
• 递增子序列（可以不连续）：这就是著名的最长递增子序列（Longest Increasing Subsequence, LIS）问题。同样对于[1, 3, 2, 4]，我们可以选出[1, 2, 4]或[1, 3, 4]，长度都为3。求解这个问题需要动态规划（DP）或贪心+二分查找，复杂度可以是 O(N²) 或 O(N log N)。

从“蓝桥杯国赛”的定位和“签到题”的标签来看，考察连续递增子序列的可能性更大，因为其思维和编码复杂度更适合作为开场题。但作为负责任的解析，我们必须掌握这两种情况。在实际比赛中，务必仔细阅读题目给出的样例输入输出，这是判断题意最直接的依据。

2.2 输入输出格式与边界条件

一道好的算法题，其难点不仅在于核心逻辑，更在于对边界情况的处理。对于这道题，我们需要明确：

1. 输入格式：通常第一行是整数 N，代表序列长度。第二行是 N 个用空格隔开的整数，代表序列 A。例如：

   5 1 3 2 4 5

2. 输出格式：一个整数，表示最长递增序列的长度。
3. 数据范围：这是选择算法的关键。如果 N <= 10^3，那么 O(N²) 的DP解法是安全的。如果 N <= 10^5 甚至更大，就必须使用 O(N log N) 的优化算法。作为国赛签到题，N 通常不会太大，但养成关注数据范围的习惯至关重要。
4. 边界条件：
   • 序列长度为 0 或 1 时，结果应为 0 或 1。
   • 序列中所有元素都相等（严格递增下无递增对），结果应为 1（单个元素本身视为长度为1的序列）。
   • 序列完全递减，结果也为 1。

把这些都想清楚，你的代码才能健壮，才能应对评测系统的所有测试点。

3. 方案设计与算法选型

基于上面的分析，我们针对两种可能的题意，设计不同的解决方案。

3.1 方案一：连续递增子序列（一次遍历法）

如果题目确定是求连续的递增子序列，那么解法非常直观，也最符合“签到题”的定位。

核心思路：顺序扫描整个序列，用一个计数器current_len记录当前正在考察的递增连续段的长度，用max_len记录全局最大长度。

1. 初始化max_len = 1,current_len = 1（至少一个元素本身）。
2. 从第二个元素开始遍历（下标 i = 1）： a. 比较A[i]和A[i-1]。 b. 如果A[i] > A[i-1]，说明仍在递增段内，current_len加1，然后更新max_len = max(max_len, current_len)。 c. 如果A[i] <= A[i-1]，说明递增段中断，重置current_len = 1，以当前元素作为新段的开始。
3. 遍历结束后，max_len即为答案。

算法复杂度：时间复杂度 O(N)，空间复杂度 O(1)。效率极高。代码示例（Java）：

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } if (n == 0) { System.out.println(0); return; } int maxLen = 1; int currentLen = 1; for (int i = 1; i < n; i++) { if (arr[i] > arr[i - 1]) { currentLen++; maxLen = Math.max(maxLen, currentLen); } else { currentLen = 1; // 递增中断，重新开始计数 } } System.out.println(maxLen); sc.close(); } }

3.2 方案二：最长递增子序列 - LIS（动态规划法）

如果题目求的是非连续的LIS，这就是一个经典的动态规划问题。对于“签到题”来说稍显复杂，但作为国赛题也完全有可能。

核心思路（O(N²) DP）：

1. 定义状态：dp[i]表示以第i个元素（下标 i）结尾的最长递增子序列的长度。
2. 状态转移方程：为了求dp[i]，我们需要看i之前的所有位置j (0 <= j < i)。如果A[i] > A[j]，说明A[i]可以接在A[j]结尾的子序列后面，形成一个更长的子序列。因此，dp[i] = max(dp[j] + 1)，对于所有满足A[i] > A[j]的 j。如果没有这样的 j，那么dp[i] = 1（只有自身）。
3. 最终答案：max(dp[0], dp[1], ..., dp[n-1])。

算法复杂度：时间复杂度 O(N²)，空间复杂度 O(N)。在 N 较大时（如 > 5000）可能超时。代码示例（Java）：

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } int[] dp = new int[n]; int ans = 0; for (int i = 0; i < n; i++) { dp[i] = 1; // 初始化为1，至少包含自己 for (int j = 0; j < i; j++) { if (arr[i] > arr[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } ans = Math.max(ans, dp[i]); } System.out.println(ans); sc.close(); } }

3.3 方案三：最长递增子序列 - LIS（贪心+二分查找法）

这是求解LIS的最优算法，能将复杂度降至 O(N log N)。其思路更为巧妙，理解起来是算法能力的一个体现。

核心思路： 我们维护一个数组tail（或d），tail[len]表示长度为 len+1 的所有递增子序列中，结尾元素最小的那个子序列的结尾元素值。这个数组本身是递增的。

1. 遍历原序列中的每个元素x。
2. 在tail数组中寻找第一个大于等于x的元素的位置。这个过程可以用二分查找。
   • 如果找不到（即x比所有tail中的元素都大），说明x可以延长当前最长的子序列，将其追加到tail末尾，相当于发现了更长的LIS。
   • 如果找到了，假设位置为pos，则用x替换tail[pos]。因为对于同样长度的递增子序列，结尾元素越小，未来“接纳”新元素、形成更长序列的潜力就越大。
3. 遍历完成后，tail数组的实际长度（即最后一个有效元素的下标+1）就是LIS的长度。

算法复杂度：时间复杂度 O(N log N)，空间复杂度 O(N)。代码示例（Java）：

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } int[] tail = new int[n]; // 辅助数组 int len = 0; // 当前tail数组的有效长度，也即当前找到的LIS长度 for (int num : arr) { // 二分查找在tail[0...len-1]中寻找第一个 >= num 的位置 int left = 0, right = len; while (left < right) { int mid = left + (right - left) / 2; if (tail[mid] < num) { left = mid + 1; } else { right = mid; } } // left 就是需要插入或替换的位置 tail[left] = num; if (left == len) { len++; // 如果插在了末尾，说明序列长度增加了 } } System.out.println(len); sc.close(); } }

注意：这个算法得到的tail数组并不一定是真实的LIS，但其长度一定等于LIS的长度。这是贪心策略的典型特征：我们只关心长度这个最优值，而不关心具体构成。

4. 实战编码与调试技巧

知道算法原理和写出能在竞赛环境中稳定得分的代码是两回事。下面我结合这道题，分享几个实战编码技巧。

4.1 输入输出优化

在Java中，Scanner虽然方便，但在读取大量数据时（比如 N=10^5）可能成为性能瓶颈。在蓝桥杯等竞赛中，更推荐使用BufferedReader和StreamTokenizer或StringTokenizer进行快速输入。

优化后的输入代码片段：

import java.io.*; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static String next() throws IOException { while (st == null || !st.hasMoreTokens()) { st = new StringTokenizer(br.readLine()); } return st.nextToken(); } static int nextInt() throws IOException { return Integer.parseInt(next()); } public static void main(String[] args) throws IOException { int n = nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = nextInt(); } // ... 后续计算逻辑 // 输出直接用 System.out.println(); } }

4.2 边界条件处理的艺术

很多同学代码逻辑主体是对的，却丢分在边界情况。处理边界，有两种风格：

1. 特判前置：在主要逻辑开始前，先把明显的边界情况处理掉并返回。代码清晰，避免主逻辑被一堆if污染。

   if (n == 0) { System.out.println(0); return; } if (n == 1) { System.out.println(1); return; }

2. 逻辑包容：设计主逻辑时，让其自然兼容边界情况。例如在方案一的遍历法中，我们从i=1开始，maxLen和currentLen初始化为1，这样当n=1时，循环不会进入，直接输出1，也是正确的。这种方式更简洁。

选择哪种取决于个人习惯和题目复杂度。对于简单题，逻辑包容更优雅；对于复杂题，特判前置更安全。

4.3 调试与测试用例设计

不要依赖题目给的样例。自己设计测试用例是必备技能。

• 基础用例：[1],[1,1,1],[5,4,3,2,1](完全递减)。
• 典型用例：[1,3,2,4,5](连续最长是3， LIS是4)。
• 边界用例：空数组（如果题目允许），超大N的随机数组（测试性能）。
• 易错用例：[2,2,3,1,2,3,4]。对于连续递增，最长是[1,2,3,4]长度为4；对于LIS，也是4 ([2,3,4]? 不，可以是[2,3,4]但注意第一个2和第二个2... 严格递增下，[2,3,4]长度为3，但[1,2,3,4]是4)。这个用例能很好地测试你对“严格递增”和起始点的处理。

在本地用这些用例跑通你的所有方案（连续方案和LIS方案），确保万无一失。

5. 从“签到题”延伸的算法思维

这道题虽然可能简单，但它像一把钥匙，能打开一扇通往更复杂算法世界的大门。我们不应该满足于AC（Accept，通过），而应该进行延伸思考。

5.1 变种问题

1. 最长不下降子序列（非递减）：只需将状态转移或比较条件中的>改为>=。在贪心+二分算法中，二分查找的目标要变为“第一个大于x的元素”（而不是大于等于），因为相等元素可以接在后面。
2. 输出具体的LIS序列：动态规划方法可以轻松回溯。我们只需在计算dp[i]时，额外记录一下是从哪个j转移过来的（pre[i] = j）。计算完后，从使dp值最大的位置开始，根据pre数组向前回溯即可。贪心+二分法要输出具体序列比较麻烦，通常需要额外记录。
3. 方案数问题：求最长递增子序列的个数。这需要在动态规划的基础上，再维护一个计数数组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]等于最大长度的i，求和其cnt[i]。

5.2 竞赛策略与心态

这道题带给我们的竞赛启示：

• “签到题”不“简单”：它考察的是基本功的扎实程度和思维的严谨性。读题、审题、考虑边界，一个环节出错就可能WA（Wrong Answer）。
• 先暴力，再优化：如果一时想不到最优解（比如O(N log N)的LIS），先写出一个正确的朴素解法（O(N²) DP）。在蓝桥杯的部分得分赛制中，这可能也能拿到可观的分数。有了保底分，心态会更稳。
• 模板化训练：像LIS（O(N log N)）这种经典算法，应该做到像写“Hello World”一样熟练。平时整理自己的算法模板库，竞赛时才能信手拈来。

6. 常见错误与问题排查

即使思路正确，编码时也常会掉进一些坑里。下面我列一个速查表，帮你快速排雷。

错误现象	可能原因	排查与解决方法
样例通过，提交后部分WA	1. 边界条件未处理（如n=0）。 2. 题意理解偏差（连续 vs 不连续）。 3. 数组开小了（特别是Java，需注意输入数据范围）。	1. 仔细设计并测试边界用例。 2. 重新审题，对照样例仔细分析。 3. 根据题目给出的最大N定义数组大小，可适当留一点余量（如+10）。
输出结果总是少1	1. 初始化长度变量为0，但单个元素序列长度应为1。 2. 在连续序列判断中，重置currentLen时逻辑错误。	1. 牢记：空序列长度为0，任何非空序列至少有一个长度为1的子序列（该元素本身）。 2. 调试时打印currentLen和maxLen的变化过程。
使用贪心+二分法，结果错误	1. 二分查找的边界条件写错（left < right还是left <= right）。 2. 查找条件写错（找“大于等于”还是“大于”）。 3.tail数组更新逻辑错误。	1. 使用最熟悉的二分模板，并牢记查找“第一个大于等于x”的写法。 2. 严格递增LIS找“第一个大于等于x”，非递减找“第一个大于x”。 3. 用一个小数组（如[3,1,2,4]）手动模拟算法过程，与代码输出对比。
大数据量下运行超时	使用了 O(N²) 的DP解法处理大规模数据。	1. 检查题目数据范围。如果 N > 10^4，优先考虑 O(N log N) 解法。 2. 检查输入输出是否使用了慢速的Scanner/System.out.println，考虑优化。
内存超限	1. 定义了不必要的二维数组。 2. 递归深度过深（本题一般不会）。	1. 优化空间，本题DP只需一维数组。 2. 将递归改为迭代。

我个人在刷这类题时的一个深刻体会是：往往不是算法不会，而是“手滑”。比如把>写成>=，把循环初始条件i=1写成i=0。避免这种错误的最好方法，除了细心，就是模块化和测试驱动。把输入、核心计算、输出分开；写完一个函数就立刻用简单用例测试。在竞赛紧张的环境中，清晰的代码结构是你最可靠的盟友。

这道“递增序列”签到题，就像一面镜子，照出我们算法基础是否扎实，编程习惯是否良好。把它研究透，意义远大于解决一道难题。下次再看到“签到题”，希望你心里想的是：“稳了，这是我的节奏。”而不是“完了，千万别是坑。”