到O(nlogn)的优化之路)
1. 最长公共子序列问题入门
第一次接触最长公共子序列（LCS）问题时，我正为一个DNA序列比对项目头疼。当时面对两个长达数万的字符串，跑了一晚上程序都没出结果，这才意识到算法优化的重要性。LCS问题看似简单——找出两个序列共有的最长子序列（不要求连续），但它的解法却蕴含着算法设计的精髓。
最直观的解法是暴力枚举，但时间复杂度高达O(2^n)。后来我发现动态规划(DP)才是解决这类问题的银弹。经典的DP解法构建一个二维表格dp[i][j]，表示序列A前i个元素和序列B前j个元素的最长公共子序列长度。状态转移方程分两种情况：
- 当A[i]=B[j]时，dp[i][j] = dp[i-1][j-1] + 1
- 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
这个解法时间复杂度O(n²)，空间复杂度O(n²)。对于小规模数据完全够用，但遇到我项目中的长序列时就力不从心了。更糟的是，当需要还原具体的最长公共子序列时，还不得不使用这个"笨重"的二维数组方案。
2. 空间优化：从O(n²)到O(n)的蜕变
2.1 滚动数组的魔法
在优化空间复杂度时，我发现了一个关键观察点：计算dp[i][j]时，只需要前一行的数据（dp[i-1][...]）和当前行已计算的部分。这意味着我们根本不需要存储整个二维数组！这就是滚动数组（Rolling Array）技术的用武之地。
具体实现时，我们只需要两行数组：
- 一行保存前一行的结果（pre）
- 一行记录当前行的计算结果（now）
每计算完一行，就交换两个数组的引用。这样空间复杂度直接从O(n²)降到了O(n)。不过要注意，这种方法只能求出LCS的长度，无法还原具体序列。下面是核心代码片段：
int dp[2][MAXN]; // 只需两行 void LCS_optimized(int n, int m) { int pre = 0, now = 1; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(a[i] == b[j]) dp[now][j] = dp[pre][j-1] + 1; else dp[now][j] = max(dp[now][j-1], dp[pre][j]); } swap(pre, now); // 交换行引用 } cout << dp[pre][m] << endl; }2.2 进一步优化的可能性
有读者可能会问：能不能只用一行数组？理论上是可以的，但需要更谨慎的处理顺序。如果从左往右计算，会覆盖还需要使用的pre行数据。这时可以采用从右往左计算的方式：
int dp[MAXN]; // 单行数组 void LCS_single_row(int n, int m) { for(int i=1; i<=n; i++) { int prev = 0; // 保存左上角的值 for(int j=1; j<=m; j++) { int temp = dp[j]; if(a[i] == b[j]) dp[j] = prev + 1; else dp[j] = max(dp[j], dp[j-1]); prev = temp; } } cout << dp[m] << endl; }这种单行数组的方案虽然更省空间，但代码可读性会降低，在实际项目中需要权衡取舍。
3. 时间复杂度突破：从O(n²)到O(nlogn)
3.1 问题转化的艺术
当我在处理两个长度为10⁵的排列时，O(n²)的算法完全无法胜任。这时我发现了LCS问题的一个特殊情形：当两个序列都是排列（即元素不重复）时，可以将其转化为最长上升子序列(LIS)问题，而LIS存在O(nlogn)的解法。
转化思路非常巧妙：
- 为序列B建立一个位置索引：pos[B[i]] = i
- 将序列A中的每个元素替换为它在B中的位置，得到新序列C
- 对序列C求LIS，这个LIS就是原序列的LCS
为什么这样转化有效？因为LCS要求子序列在两个原序列中的相对顺序一致，而LIS正好保持了这种顺序性。
3.2 LIS的O(nlogn)解法
LIS的经典解法使用贪心+二分查找。维护一个数组lower，其中lower[i]表示长度为i+1的上升子序列的最小末尾元素。遍历序列时：
- 如果当前元素大于lower的最后一个元素，直接追加
- 否则，用二分查找找到第一个不小于当前元素的位置并替换
int LIS(vector<int>& nums) { vector<int> lower; for(int num : nums) { auto it = lower_bound(lower.begin(), lower.end(), num); if(it == lower.end()) lower.push_back(num); else *it = num; } return lower.size(); }将LCS转化为LIS后，整体时间复杂度降为O(nlogn)，这在处理大规模数据时优势明显。我在那个DNA项目中应用这个优化后，运行时间从小时级降到了秒级。
4. 实战应用与边界情况
4.1 不同场景下的算法选择
在实际项目中，我们需要根据具体需求选择算法：
- 当需要还原具体LCS时：只能使用经典O(n²)空间解法
- 只需知道长度且空间紧张时：使用O(n)空间的滚动数组
- 处理排列且数据量大时：优先考虑O(nlogn)的LIS转化法
我曾在一个文本差异比对工具中遇到一个有趣案例：两个文本的LCS长度接近文本本身长度。这时O(n²)算法反而更快，因为大部分情况下直接匹配，很少进入else分支。这说明算法选择不能只看理论复杂度，还要考虑实际数据特征。
4.2 处理重复元素的技巧
当序列中存在重复元素时，LCS转LIS的方法需要调整。一个实用的解决方案是为每个值维护一个位置列表，并在构造序列C时按倒序处理：
unordered_map<int, vector<int>> pos_map; // 填充pos_map，记录每个值在B中的所有位置（降序） for(int i=m; i>=1; i--) { pos_map[B[i]].push_back(i); } vector<int> C; for(int ai : A) { if(pos_map.count(ai)) { for(int p : pos_map[ai]) { C.push_back(p); } } } // 然后对C求LIS这种方法虽然增加了预处理开销，但仍能保持O(nlogn)的整体时间复杂度。我在一个代码抄袭检测系统中就采用了这种改进，成功处理了包含大量重复标识符的源代码比对。
