子序列问题
前言
笔者曾经参加头条的面试，面试官在算法环节问的就是这个问题，首先问了我连续子序列的情形，之后改为一般子序列。一般面试算法都是这种循序渐进的方式，先给出一个简单情形，接着将问题提升，并不断优化。题目不一定很难，主要考核面试者的应变和分析能力。可惜当时对算法理解还是过于浅显，作为总结写下这篇文章。
连续子列问题
最大子序和
问题描述：
求给定序列的所有连续子序列的最大和
分析
如果一个连续的子序列它的头部和负(即以起点开始的连续子列)，则将头部丢去后得到的序列和更大。因此，每当有头部和负时，置总和为0，表示从新开始累计求和，更新总和后也同时更新最大和的值。
代码：
int sum = 0;
int res = -INF;
for (int i = 0; i < N; i++) {
sum += nums[i];
res = Math.max(res, sum);
if (sum < 0)
sum = 0;
}
有长度限制的子序和
加入长度限制，这里有两种条件。一种是长度不大于m,另一种是长度不小于m。
无论哪种情况，都可以预处理出前缀和，这样可以在$O(1)$时间求出某一子段的和。
长度不大于m
相当于一个不大于m的滑动窗口，每次有元素sum[i]将要入队时，求子序列以其作为结尾，则子序列头需要尽可能的小。这个最小值是从大小为m的窗口中选取的，这个问题可以用单调队列维护一个滑动窗口的最小值来实现。
代码：
int head = 0, tail = -1;
int res = 0xcfcfcfcf;
for (int i = 1; i <= n; i++) {
if (i - q[head] > m)
head++;
res = Math.max(res, s[i] - s[q[head]]);
while (head <= tail && s[i] <= s[q[tail]]) {
tail--;
}
q[++tail] = i;
}
长度不小于m
方法一
枚举结束点，则起始点必须满足$j + m - 1 <= i$，则等价于求下式的值：
$$
\max_{m<=i <n}\{sum_i - \min_{j + m - 1 <= i}(sum_j)\}
$$
代码：
for (int i = m; i <= n; i++) {
int min = INF;
for (int j = 0; j + m - 1 <= i; j++)
min = Math.min(min, s[j]);
res = Math.max(res, s[i] - min);
}
算法复杂度： $O(n ^ 2)$
方法二
方法一中，为了求满足条件的起始点，需要从头开始的扫描，但每当i的指针加1时，$sum_j$只多了一个，因此可以动态维护满足起始点的最小值。
代码：
int min = INF;
for (int i = m; i <= n; i++) {
min = Math.min(min, s[i - m]);
res = Math.max(res, s[i] - min);
}
不重复子序列
问题描述：
求给定序列不重复子序列的最大长度，即子序列中每个元素只出现一次
分析
当序列中新增添一个元素a时，如果不满足不重复性，则存在和a相同的元素，如果想要子序列以a结尾，则至少起始指针从与a相同元素的后一个开始。
方法
双指针算法，记录两个指针位置$i,j$分别表示结束和开始下标。当遇到重复元素时，移动$j$直到$i$到$j$的窗口内不含有重复元素。
算法复杂度：$O(n)$
代码：
int res = 1;
for (int i = 0, j = 0; i < n; i++) {
count[nums[i]]++;
while (count[nums[i]] > 1) {
count[nums[j]]--;
j++;
}
res = Math.max(res, i - j + 1);
}
这个算法的起始指针是步进的方式，还可以用一个map来存储元素和下标，这样在遇到重复元素时，可以直接跳到合法的最小位置。
上升子序列问题
原问题
问题描述：
求一个给定序列的严格上升子序列的长度
方法：
动态规划
用$dp[i]$表示以下标$i$结尾的子序列的最大长度，显然状态转移需要从下标小于$i$且序列结尾小于$a[i]$的那些序列中选择。
代码：
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (a[i] > a[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
想要求出最大长度只需枚举结尾下标即可，当然也可以在更新dp的同时，也同时维护一个最大长度。
算法复杂度： $O(n^2)$
单调队列优化
在前一个问题中发现能否状态转移之和前序列的尾有关，因此可以用一个数组$last [\ ]$来存储以每个长度下，最小需要多大才能对接到前子序列。
长度更长的序列是由较短序列构成的因此有: $last[i] < last[j] \quad when \ i < j$
$last$数组现在成为了单调队列，在新加一个数$a[ i]$时，该数可以在$last$数组选择一个比它大的第一个数，在长度不变下，如果以$a[i ]$更新，结尾变小，更容易被加长。在选择合适的放置位置时，可以用二分。
代码：
queue[0] = 0xcfcfcfcf;
int len = 0;
for (int i = 0; i < n; i++) {
int l = 0;
int r = len;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (queue[mid] < a[i])
l = mid;
else
r = mid - 1;
}
len = Math.max(len, r + 1);
queue[r + 1] = a[i];
}
注意这里下标的具体含义，选择合适的二分方式，$queue[0 ]$是设置的一个虚拟头节点。
算法复杂度: $O(n\log n)$
最大上升子序和
$dp[i]$表示以$i$结尾上升子序列的最大和，状态转移也是显然的。
代码：
for (int i = 0; i < N; i++) {
dp[i] = nums[i];
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + nums[i]);
}
}
}
长度越长不代表子序和越大，所以无法用单调队列优化。
公共子序列问题
最长公共子序列
问题描述：
求字符串a,b的最长公共子序列的长度
方法：
动态规划，$dp[i][j]$表示$a$的前$i$个字符，$b$的前$j$个字符中的最大公共子序列长度。
状态转移方程：
$$
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
$$
当a[i] 和b[j]相同时，多了一条转移路线。
$$
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)\quad if \ a[i] = b[j]
$$
代码：
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
if (a.charAt(i) == b.charAt(j))
dp[i + 1][j + 1] = Math.max(dp[i + 1][j + 1], dp[i][j] + 1);
}
}
最长公共上升子序列
与上一问题相比增加了上升的约束。
解题方式依旧是动态规划，这次$dp[i][j]$表示的是$A$的前$i$个和$B$的以$j$结尾的公共上升子序列长度最大值。
这里引入了不对称的表示，第一维是前i个，第二维是以j结尾，后者约束更强。
代码：
for (int i = 1; i <= N; i++) {
for (int j = 1; j <=N; j++) {
dp[i][j] = dp[i - 1][j];
if (A[i] == B[j]) {
dp[i][j] = Math.max(1, dp[i][j]);
for (int k = 1; k < j; k++) {
if (B[k] < B[j])
dp[i][j] = Math.max(dp[i][j], dp[i - 1][k] + 1);
}
}
}
}
总结
通过上面几个子序列模型，学习了相应的解决办法。往往只是增加了一个约束条件后，问题的求解方式完全不同。
我们用了动态规划，双指针，单调队列优化，希望仔细体会不同问题细微差别，在遇到新的问题学会知识迁移。
