算法竞赛入门：从蓝桥杯签到题看最长递增子序列（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 输入输出格式与边界条件一道好的算法题其难点不仅在于核心逻辑更在于对边界情况的处理。对于这道题我们需要明确输入格式通常第一行是整数 N代表序列长度。第二行是 N 个用空格隔开的整数代表序列 A。例如5 1 3 2 4 5输出格式一个整数表示最长递增序列的长度。数据范围这是选择算法的关键。如果 N 10^3那么 O(N²) 的DP解法是安全的。如果 N 10^5 甚至更大就必须使用 O(N log N) 的优化算法。作为国赛签到题N 通常不会太大但养成关注数据范围的习惯至关重要。边界条件序列长度为 0 或 1 时结果应为 0 或 1。序列中所有元素都相等严格递增下无递增对结果应为 1单个元素本身视为长度为1的序列。序列完全递减结果也为 1。把这些都想清楚你的代码才能健壮才能应对评测系统的所有测试点。3. 方案设计与算法选型基于上面的分析我们针对两种可能的题意设计不同的解决方案。3.1 方案一连续递增子序列一次遍历法如果题目确定是求连续的递增子序列那么解法非常直观也最符合“签到题”的定位。核心思路顺序扫描整个序列用一个计数器current_len记录当前正在考察的递增连续段的长度用max_len记录全局最大长度。初始化max_len 1,current_len 1至少一个元素本身。从第二个元素开始遍历下标 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以当前元素作为新段的开始。遍历结束后max_len即为答案。算法复杂度时间复杂度 O(N)空间复杂度 O(1)。效率极高。代码示例Javaimport 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定义状态dp[i]表示以第i个元素下标 i结尾的最长递增子序列的长度。状态转移方程为了求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只有自身。最终答案max(dp[0], dp[1], ..., dp[n-1])。算法复杂度时间复杂度 O(N²)空间复杂度 O(N)。在 N 较大时如 5000可能超时。代码示例Javaimport 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或dtail[len]表示长度为 len1 的所有递增子序列中结尾元素最小的那个子序列的结尾元素值。这个数组本身是递增的。遍历原序列中的每个元素x。在tail数组中寻找第一个大于等于x的元素的位置。这个过程可以用二分查找。如果找不到即x比所有tail中的元素都大说明x可以延长当前最长的子序列将其追加到tail末尾相当于发现了更长的LIS。如果找到了假设位置为pos则用x替换tail[pos]。因为对于同样长度的递增子序列结尾元素越小未来“接纳”新元素、形成更长序列的潜力就越大。遍历完成后tail数组的实际长度即最后一个有效元素的下标1就是LIS的长度。算法复杂度时间复杂度 O(N log N)空间复杂度 O(N)。代码示例Javaimport 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虽然方便但在读取大量数据时比如 N10^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 边界条件处理的艺术很多同学代码逻辑主体是对的却丢分在边界情况。处理边界有两种风格特判前置在主要逻辑开始前先把明显的边界情况处理掉并返回。代码清晰避免主逻辑被一堆if污染。if (n 0) { System.out.println(0); return; } if (n 1) { System.out.println(1); return; }逻辑包容设计主逻辑时让其自然兼容边界情况。例如在方案一的遍历法中我们从i1开始maxLen和currentLen初始化为1这样当n1时循环不会进入直接输出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. 从“签到题”延伸的算法思维这道题虽然可能简单但它像一把钥匙能打开一扇通往更复杂算法世界的大门。我们不应该满足于ACAccept通过而应该进行延伸思考。5.1 变种问题最长不下降子序列非递减只需将状态转移或比较条件中的改为。在贪心二分算法中二分查找的目标要变为“第一个大于x的元素”而不是大于等于因为相等元素可以接在后面。输出具体的LIS序列动态规划方法可以轻松回溯。我们只需在计算dp[i]时额外记录一下是从哪个j转移过来的pre[i] j。计算完后从使dp值最大的位置开始根据pre数组向前回溯即可。贪心二分法要输出具体序列比较麻烦通常需要额外记录。方案数问题求最长递增子序列的个数。这需要在动态规划的基础上再维护一个计数数组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 竞赛策略与心态这道题带给我们的竞赛启示“签到题”不“简单”它考察的是基本功的扎实程度和思维的严谨性。读题、审题、考虑边界一个环节出错就可能WAWrong Answer。先暴力再优化如果一时想不到最优解比如O(N log N)的LIS先写出一个正确的朴素解法O(N²) DP。在蓝桥杯的部分得分赛制中这可能也能拿到可观的分数。有了保底分心态会更稳。模板化训练像LISO(N log N)这种经典算法应该做到像写“Hello World”一样熟练。平时整理自己的算法模板库竞赛时才能信手拈来。6. 常见错误与问题排查即使思路正确编码时也常会掉进一些坑里。下面我列一个速查表帮你快速排雷。错误现象可能原因排查与解决方法样例通过提交后部分WA1. 边界条件未处理如n0。2. 题意理解偏差连续 vs 不连续。3. 数组开小了特别是Java需注意输入数据范围。1. 仔细设计并测试边界用例。2. 重新审题对照样例仔细分析。3. 根据题目给出的最大N定义数组大小可适当留一点余量如10。输出结果总是少11. 初始化长度变量为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. 将递归改为迭代。我个人在刷这类题时的一个深刻体会是往往不是算法不会而是“手滑”。比如把写成把循环初始条件i1写成i0。避免这种错误的最好方法除了细心就是模块化和测试驱动。把输入、核心计算、输出分开写完一个函数就立刻用简单用例测试。在竞赛紧张的环境中清晰的代码结构是你最可靠的盟友。这道“递增序列”签到题就像一面镜子照出我们算法基础是否扎实编程习惯是否良好。把它研究透意义远大于解决一道难题。下次再看到“签到题”希望你心里想的是“稳了这是我的节奏。”而不是“完了千万别是坑。”