最长公共子序列和最长递增子序列是常见的子序列考题，非常经典。

    LCS的状态转移方程和Edit distance几乎一样，如果要回溯LCS，则需要一个容器记录路径即可。

    1. int LCS(const string& s, const string& t,string& lcs) {
    2.         if (s.empty() || t.empty()) return -1;
    3.         int m = s.size();
    4.         int n = t.size();
    5.         vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    6.         vector<vector<string>> map(m + 1, vector<string>(n + 1, "."));
    7.         for(int i=1;i<=m;++i){
    8.             for (int j = 1; j <= n; ++j) {
    9.                 if (s[i - 1] == t[j - 1]) {
    10.                     dp[i][j] = dp[i - 1][j - 1] + 1;
    11.                     map[i][j] = "\\";
    12.                 }
    13.                 else if (dp[i-1][j]>=dp[i][j-1])
    14.                 {
    15.                     dp[i][j] = dp[i - 1][j];
    16.                     map[i][j] = "|";
    18.                 }else {
    19.                     dp[i][j] = dp[i][j - 1];
    20.                     map[i][j] = "-";
    21.                 }
    22.             }
    23.         }
    24.         if (dp[m][n] == 0)
    25.             return 0;
    26.         //回溯出LSC总串
    27.         int i = m, j = n;
    28.         while (i > 0 && j > 0) {
    29.             if (map[i][j] == "\\") {
    30.                 lcs.push_back(s[i-1]);
    31.                 --i;
    32.                 --j;
    33.             }
    34.             else if (map[i][j] == "|")
    35.                 --i;
    36.             else
    37.                 --j;
    38.         }
    39.         reverse(lcs.begin(), lcs.end());
    40.         return dp[m][n];
    41.     }

    LIS不要求回溯出子序列，则比较简单，用单调栈+二分搜索。

    1. int lis(vector<int>& arr){
    2.     vector<int> stk;//递增栈
    3.     for(int i=0;i<arr.size();++i){
    4.          if(stk.empty()||stk.back()<arr[i]){//因为严格递增，所以等于无法入栈
    5.             stk.emplace_back(arr[i]);
    6.         }else{
    7.              *lower_bound(stk.begin(),stk.end(),arr[i])=arr[i];
    8.         }
    9.     }
    10.     return stk.size();
    11. }