最长上升子序列(LIS)
1. \mathcal{O}(n^2) 做法
设 dp_{i} 表示以i 结尾的答案。所以先枚举一个 i ，再从1 开始枚举 j ，每次看到小于 a_{j} 的数，取一个最大的更新 dp_{i} 。
2. \mathcal{O}(nlog_n) 做法
状态设计： dp_i 表示长度为 i 的最长上升子序列的最小末尾值。
思想解读：一条上升子序列长度确定，末尾越小越容易使一个元素在后面加入。
两个序列中的最长公共子序列(LCS)
1. \mathcal{O}(n^2) 做法
设 dp_{i,j} 表示第一个序列前 i 位，第二个序列前 j 位的解的长度。
如果当前的 A_i = B_i 则 dp_{i,j} = max(dp_{i – 1, j – 1}+1, dp_{i, j})
如果当前的 A_i \neq B_i 则 dp_{i,j} = max(dp_{i-1,j}, dp_{i,j-1})
2. \mathcal{O}(nlog_n) 做法
考虑一个 map ，表示 A_i 在 B 中的位置。
如果 A_i 在 B 中递增，则考虑它。
第二个序列为第一个序列的最小子串的子序列问题
1. \mathcal{O}(n^2) 做法
直接暴力枚举 l 向右匹配。
2. \mathcal{O}(n) 做法
考虑到每种字符在 t 中至多出现一次，所以每个字符往后想要跳到什么字符是固定的，因此并不用对每个位置维护一个长度为 mm 的数组。
不难发现 s 出现次数最少的 t_i 是不会超过 \frac{n}{m} 次的。因此我们令 c 表示在 t 中出现且在 s 中出现次数最少的字符，然后把选择每个等于 t_1 的位置开始做改成每个等于 c 的位置，然后同时向前向后跳。
时间复杂度 \mathcal{O}(\frac{n}{m} \cdot m) = \mathcal{O}(n)。
3. \mathcal{O}(n) 做法
考虑使用 m-pointers。从后往前枚举 l，然后同时维护一个长度为 m 的数组 p，表示当前 l 开始，往后 t 中的所有字符，会在 s 中的哪里匹配。不难发现 p_i 会更新当且仅当 p_{i−1} 有更新。因此每次我们直接暴力更新一个前缀即可。
不难发现 s 中每个字符至多被匹配一次，因此时间复杂度 O(n)。
