本文共 5143 字，大约阅读时间需要 17 分钟。
1. LIS (Longest Increasing Subsequence)
O (n^2)：
/* LIS(Longest Increasing Subsequence) 最长上升子序列 O (n ^ 2) 状态转移方程：dp[i] = max (dp[j]) + 1 (a[j] < a[i]，1 <= j < i) 附带有print输出路径函数*/void LIS(void) { int ret = 0, last = 0; for (int i=1; i<=n; ++i) { dp[i] = 1; fa[i] = -1; for (int j=1; j
O (nlogn)：
/* LIS 二分查找优化, O(nlogn) 设当前最长递增子序列为len，考虑元素a[i]; 若d[len]
res; int i; for (i=pos[len]; ~fa[i]; i=fa[i]) res.push_back (a[i]); res.push_back (a[i]); for (int i=res.size ()-1; i>=0; --i) printf ("%d%c", res[i], i == 0 ? '\n' : ' ');}
2. LCS (Longest Common Subsequence)
/* LCS(Longest Common Subsequence)： 状态转移方程：dp[i][j] = dp[i-1][j-1] + 1; (s[i-1] == t[i-1]) dp[i][j] = max (dp[i][j-1], dp[i-1][j]);(s[i-1] != t[i-1]) 可滚动数组优化。附带有print输出路径函数。*/void LCS(void) { memset (dp, 0, sizeof (dp)); memset (fa, 0, sizeof (fa)); for (int i=0; i<=lens; ++i) fa[i][0] = -1; for (int i=0; i<=lent; ++i) fa[0][i] = 1; for (int i=1; i<=lens; ++i) { for (int j=1; j<=lent; ++j) { if (s[i-1] == t[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; fa[i][j] = 0; } else if (dp[i-1][j] >= dp[i][j-1]) { dp[i][j] = dp[i-1][j]; fa[i][j] = -1; } else { dp[i][j] = dp[i][j-1]; fa[i][j] = 1; } } } printf ("%d\n", dp[lens][lent]); print (lens, lent); puts ("");}void print(int x, int y) { if (!x && !y) return ; if (fa[x][y] == 0) { print (x-1, y-1); printf ("%c", s[x-1]); } else if (fa[x][y] == -1) { print (x-1, y); printf ("%c", s[x-1]); } else { print (x, y-1); printf ("%c", t[y-1]); }}
3. LCIS (Longest Common Increasing Subsequence)
/* LCIS(Longest Common Increasing Subsequence) 最长公共上升子序列 状态转移方程：a[i] != b[j]: dp[i][j] = dp[i-1][j]; a[i] == b[j]: dp[j]=max(dp[j],dp[k]); (1<=k b[j] && dp[i][j] > dp[i][k]) k = j; //找到最优的k if (ret < dp[i][j]) { ret = dp[i][j]; //更新所有dp中的最大值 sx = i, sy = j; } } } printf ("%d\n", ret); fir = true; print (sx, sy, -1); puts ("");}void print(int x, int y, int last) { //bool fir; if (x == 0 || y == 0) return ; print (fx[x][y], fy[x][y], y); if (y != last) { if (fir) printf ("%d", b[y]), fir = false; else printf (" %d", b[y]); }}
4. LPS (Longest Palidromic Subsequence)
/* LCS的思想，dp[i][j]表示i到j的最长回文串长度，状态转移方程： 1. dp[j][j+i-1] = dp[j+1][j+i-2] + 2; (str[j] == str[j+i-1]) 2. dp[j][j+i-1] = max (dp[j+1][j+i-1], dp[j][j+i-2]); (str[j] != str[j+i-1]) ans[1][len]是string类型，记录LPS字符*/void LPS(void) { int len = strlen (str + 1); memset (dp, 0, sizeof (dp)); for (int i=1; i<=len; ++i) dp[i][i] = 1; for (int i=1; i<=len; ++i) ans[i][i] = str[i]; for (int i=2; i<=len; ++i) { //区间长度 for (int j=1; j+i-1<=len; ++j) { //[j, j+i-1] if (str[j] == str[j+i-1]) { if (i == 2) { dp[j][j+i-1] = 2; ans[j][j+i-1] = ans[j][j] + ans[j+i-1][j+i-1]; continue; } dp[j][j+i-1] = dp[j+1][j+i-2] + 2; ans[j][j+i-1] = str[j] + ans[j+1][j+i-2] + str[j+i-1]; } else if (dp[j+1][j+i-1] > dp[j][j+i-2]) { dp[j][j+i-1] = dp[j+1][j+i-1]; ans[j][j+i-1] = ans[j+1][j+i-1]; } else if (dp[j][j+i-2] > dp[j+1][j+i-1]) { dp[j][j+i-1] = dp[j][j+i-2]; ans[j][j+i-1] = ans[j][j+i-2]; } else { dp[j][j+i-1] = dp[j+1][j+i-1]; ans[j][j+i-1] = min (ans[j+1][j+i-1], ans[j][j+i-2]); } } } int mlen = dp[1][len]; for (int i=0; i
5. MCS (Maximum Continuous Subsequence)
O (n)：
/* MCS (Maximum Continuous Subsequence) 最大子序列和 O (n) 1. DP 2. 前缀 若有多个答案输出第一个，均给出区间端点*/void MCS(int n) { int l = 0, ll = 0, rr = 0; int sum = -INF, mx = -INF; for (int i=1; i<=n; ++i) { if (sum + a[i] < a[i]) { sum = a[i]; l = i; } else sum += a[i]; if (sum > mx) { mx = sum; ll = l, rr = i; } } printf ("%d %d %d\n", mx, ll, rr);}
O (n) another:
//O (n) //anothervoid MCS(int n) { int l = 0, ll = 0, rr = 0; int sum = 0, mx = -INF, mn = 0; for (int i=1; i<=n; ++i) { sum += a[i]; if (sum - mn > mx) { mx = sum - mn; ll = l; rr = i; } if (sum < mn) { mn = sum; l = i; } } printf ("%d %d %d\n", mx, ll + 1, rr);}
O (nlogn)：
//O (nlogn) //输出端点困难int MCS(int *a, int l, int r) { if (l == r) { if (a[l] > 0) return a[l]; else return 0; } int mid = (l + r) >> 1; int lmax = MCS (a, l, mid); int rmax = MCS (a, mid + 1, r); int lbmax = 0, lbsum = 0; for (int i=mid; i>=left; --i) { //之前写错了，应该是连续的 lbsum += a[i]; if (lbmax < lbsum) lbmax = lbsum; } int rbmax = 0, rbsum = 0; for (int i=mid+1; i<=r; ++i) { rbsum += a[i]; if (rbmax < rbsum) rbmax = rbsum; } return max (lbmax + rbmax, max (lmax, rmax));}