在子序列问题中有一系列问题尤为经典，而将子序列问题加上一个连续的限制条件便转化为了子串问题，本文就这些经典问题进行总结性讨论。

最长上升子序列（LIS）

$$dp[i]= \max\limits_{1\leq j< i,value[i]>value[j]}(dp[j]+1) $$

利用序列长度作为阶段，状态为当前子序列长度，若满足序列条件则可以进行转移。

修改条件$value[i]>value[j]$易将问题转化为最长不上升子序列，最长下降子序列以及最长不下降子序列。时间复杂度$O(|S|^2)$。

其中，关于LIS的问题可以看这篇文章：

同时，关于这一类问题还有使用树状数组的解法，其时间复杂度为$O(|S|\log |S|)$，可以参考这篇文章：

子串问题

暴力计算即可，时间复杂度$O(|S|)$。

最长公共子序列（LCS）

$$dp[i][j]=\begin{cases}dp[i-1][j-1] + 1,(s[i]==s[j]) \\ \max(dp[i-1][j],dp[i][j-1]),(s[i] != s[j]) \end{cases}$$

利用两个序列长度作为阶段，如果$s[i]==s[j]$，则将问题转化为其子问题$dp[i-1][j-1]$，也就是去除掉末尾的相同字符的序列求LCS，若$s[i]!=s[j]$，则考虑其LCS为$\max(dp[i-1][j],dp[i][j-1])$，也就是分别不考虑末尾字符的序列求LCS。

时间复杂度$O(|S_{1}||S_{2}|)$。

子串问题

$$dp[i][j]=dp[i-1][j-1]+1,(s[i]==s[j])$$

相较于LCS问题，由于施加了连续这样一个限制条件，在状态转移中将不再考虑$dp[i-1][j]$与$dp[i][j-1]$两种情况（这两种情况将破坏连续性）。

时间复杂度$O(|S_{1}||S_{2}|)$。

最长回文子序列（LPS）

$$dp[i][i+len]=\begin{cases}dp[i+1][i+len-1],(s[i]==s[i+len]) \\ \max(dp[i+1][i+len],dp[i][i+len-1]),(else)\end{cases}$$

亦可将问题理解为将序列反转，对原序列与反转序列求LCS。

时间复杂度$O(|S|^2)$。

子串问题

Manacher算法在$O(|S|)$的时间复杂度下可以很好地解决这个问题。

最大子序列

暴力即可，时间复杂度$O(|S|)$。

子串问题

$$dp[i]=\begin{cases}\max(\sum_{j=last}^{i-1}value[j]+value[i],dp[i-1]),(\sum_{j=last}^{i-1}value[j]>0) \\ value[i],(\sum_{j=last}^{i-1}value[j]<=0)\end{cases}$$

更直观的来说，对于当前位置$i$，若其前面的部分连续子序列和大于零，则加上当前$value[i]$，否则重置部分连续子序列和为$value[i]$，每次处理后对答案进行维护。时间复杂度$O(|S|)$

参考代码：

int max_substring(vector<int>& a) {
  int cur_max, ret;
  if ( a.size() < 2 )
        return a[0];
  cur_max = ret = a[0];
  for ( int i = 1; i < a.size(); ++i ) {
    if ( cur_max <= 0 )
      cur_max = a[i];
       else 
      cur_max += a[i];
    
    ret = max(cur_max, ret);
  }
  
  return ret;
}

当然，本文所总结的子序列（子串）问题知识只是其中的冰山一角，只要将问题稍加组合变换便可以组成一系列新的问题，如最大k子串、最大k子序列、最长公共回文子序列等，而求解这一系列问题并不全是机械式照搬结论，更多的是需要我们发挥创造力去具体地看待每一个问题。