企业官网建设流程全解析

1. 最长公共子序列（LCS）与最长递增子序列（LIS）概述

在算法领域，子序列问题一直是经典且实用的课题。最长公共子序列（Longest Common Subsequence, LCS）和最长递增子序列（Longest Increasing Subsequence, LIS）是两个密切相关但又各具特点的问题。

LCS要解决的问题是：给定两个序列，找出它们共有的、最长的子序列。这里的子序列不需要连续，只需要保持相对顺序。例如，"ABC"和"AC"都是"ABCD"的子序列。LCS在文本相似度比较、版本控制、生物信息学中的DNA序列比对等领域有广泛应用。

LIS则是针对单个序列，寻找一个子序列使得元素严格递增且长度最长。比如序列[10, 9, 2, 5, 3, 7, 101, 18]的LIS是[2, 3, 7, 101]，长度为4。LIS在任务调度、股票分析、路径规划等场景中都有重要应用。

注意：虽然LCS和LIS名称相似，但它们是不同的问题。LCS处理两个序列的关系，而LIS处理单个序列的性质。不过有趣的是，它们可以通过动态规划这一共同的算法范式来解决。

2. LCS问题详解与实现

2.1 LCS的动态规划解法

LCS的经典解法是动态规划，其核心在于状态定义和状态转移方程。我们定义dp[i][j]表示序列A前i个元素和序列B前j个元素的LCS长度。

状态转移方程分为两种情况：

1. 当A[i] == B[j]时：dp[i][j] = dp[i-1][j-1] + 1
2. 当A[i] != B[j]时：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

这个方程直观理解就是：当当前元素匹配时，LCS长度可以增加1；当不匹配时，我们需要考虑两种可能的前驱状态中的较大值。

2.2 LCS的C++实现

#include <iostream> #include <algorithm> #include <string> using namespace std; int LCS(const string &A, const string &B) { int m = A.length(), n = B.length(); int dp[m+1][n+1] = {0}; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (A[i-1] == B[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } return dp[m][n]; } int main() { string A = "ABCBDAB"; string B = "BDCABA"; cout << "LCS length: " << LCS(A, B) << endl; return 0; }

2.3 LCS的空间优化

上述实现使用了O(mn)的空间，实际上可以优化到O(min(m,n))。我们只需要保留当前行和上一行的数据即可：

int LCS_optimized(const string &A, const string &B) { if (A.length() < B.length()) return LCS_optimized(B, A); int m = A.length(), n = B.length(); int prev[n+1] = {0}; int curr[n+1] = {0}; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (A[i-1] == B[j-1]) { curr[j] = prev[j-1] + 1; } else { curr[j] = max(prev[j], curr[j-1]); } } swap(prev, curr); } return prev[n]; }

3. LIS问题详解与实现

3.1 LIS的三种解法

LIS问题有多种解法，各有优缺点：

1. 动态规划法：时间复杂度O(n²)，空间复杂度O(n)
2. 贪心+二分法：时间复杂度O(nlogn)，空间复杂度O(n)
3. 转化为LCS法：将原序列排序去重后与原序列求LCS

3.2 动态规划解法

定义dp[i]为以第i个元素结尾的LIS长度。状态转移方程为： dp[i] = max(dp[j] + 1) for all j < i and nums[j] < nums[i]

int lengthOfLIS(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); int max_len = 1; for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } max_len = max(max_len, dp[i]); } return max_len; }

3.3 贪心+二分法（最优解）

维护一个数组tails，其中tails[i]表示长度为i+1的LIS的最小末尾元素。这个数组是单调递增的，可以用二分查找优化。

int lengthOfLIS_optimized(vector<int>& nums) { vector<int> tails; for (int num : nums) { auto it = lower_bound(tails.begin(), tails.end(), num); if (it == tails.end()) { tails.push_back(num); } else { *it = num; } } return tails.size(); }

这种方法将时间复杂度降到了O(nlogn)，是解决LIS问题的最优算法。

4. 实际应用与变种问题

4.1 LCS的应用场景

1. 文本相似度比较：比较两段代码或文档的相似度
2. 版本控制系统：Git等工具比较文件差异
3. 生物信息学：DNA序列比对
4. 拼写检查：寻找最接近的正确单词

4.2 LIS的应用场景

1. 俄罗斯套娃信封问题：二维的LIS问题
2. 最长递增路径：矩阵中的最长递增路径
3. 任务调度：寻找最多可以安排的不冲突任务
4. 股票分析：寻找最长的价格上涨序列

4.3 合唱队形问题

这是一个经典的LIS变种问题，要求找到一个位置，使得左边是递增序列，右边是递减序列。解法是对每个位置计算从左到右的LIS和从右到左的LDS（最长递减子序列），然后求和取最大值。

int chorusFormation(vector<int>& heights) { int n = heights.size(); vector<int> lis(n, 1), lds(n, 1); // 计算从左到右的LIS for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (heights[j] < heights[i]) { lis[i] = max(lis[i], lis[j] + 1); } } } // 计算从右到左的LDS for (int i = n-2; i >= 0; --i) { for (int j = n-1; j > i; --j) { if (heights[j] < heights[i]) { lds[i] = max(lds[i], lds[j] + 1); } } } int max_len = 0; for (int i = 0; i < n; ++i) { max_len = max(max_len, lis[i] + lds[i] - 1); } return n - max_len; }

5. 常见问题与优化技巧

5.1 LCS常见问题

1. 如何重建LCS而不仅仅是计算长度？可以反向追踪dp表，当A[i]==B[j]时，这个字符属于LCS，然后移动到dp[i-1][j-1]；否则移动到dp[i-1][j]和dp[i][j-1]中较大的那个。

2. 如何处理多个序列的LCS？对于k个序列的LCS，时间复杂度会上升到O(n^k)，通常需要特殊的优化或近似算法。

5.2 LIS常见问题

1. 如何重建LIS序列？除了维护dp数组，还需要维护一个parent数组记录前驱节点。

2. 如何处理非严格递增的LIS？只需将比较条件从nums[j] < nums[i]改为nums[j] <= nums[i]。

5.3 性能优化技巧

1. 滚动数组优化：对于LCS，可以使用两行数组代替整个二维数组。
2. 离散化处理：对于LIS，如果数值范围很大，可以先离散化。
3. 记忆化搜索：有时递归+记忆化的写法比迭代更直观。
4. 并行计算：对于大规模数据，可以考虑并行化部分计算。

6. 算法扩展与进阶

6.1 二维LIS问题

如俄罗斯套娃信封问题，需要先对一维排序，然后在另一维上求LIS：

int maxEnvelopes(vector<vector<int>>& envelopes) { sort(envelopes.begin(), envelopes.end(), [](const auto& a, const auto& b) { return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0]; }); vector<int> tails; for (const auto& env : envelopes) { int h = env[1]; auto it = lower_bound(tails.begin(), tails.end(), h); if (it == tails.end()) { tails.push_back(h); } else { *it = h; } } return tails.size(); }

6.2 带权值的LIS

每个元素有权值，求权值和最大的递增子序列：

int weightedLIS(vector<int>& nums, vector<int>& weights) { int n = nums.size(); vector<int> dp(weights.begin(), weights.end()); int max_sum = dp[0]; for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + weights[i]); } } max_sum = max(max_sum, dp[i]); } return max_sum; }

6.3 分治解法

对于某些特殊情况的LIS问题，可以考虑使用分治法，将问题分解为更小的子问题。

在实际工程应用中，选择哪种算法取决于具体场景和数据规模。对于小规模数据，简单的动态规划就足够；对于大规模数据，则需要使用更高效的算法如贪心+二分。