[link](https://blog.csdn.net/ltrbless/article/details/81318935)
by Liyhzh_C202712 @ 2024-04-27 18:11:24
[link](https://www.cnblogs.com/moomcake/p/9385170.html)
by Liyhzh_C202712 @ 2024-04-27 18:12:07
@[Liyhzh_C202712](/user/1068500) 感谢！！！已关
by I_like_play_eggy @ 2024-04-27 18:17:04
@[I_like_play_eggy](/user/1126325) 已互关。
by Liyhzh_C202712 @ 2024-04-27 18:19:19
不是详讲，但短小精悍，有问题问我
LIS：
对于第 $a_i$ 的 LIS，相当于 $\max\limits_{j \lt i,a_j \lt a_i}\{a_j\}+1$，可以离散化后，用权值树状数组维护最大值。
LCS:
对于[这道题](/problem/P1439)来说，将数组重新标号，让 $a$ 严格递增，如：
```
3 1 2 5 4
5 2 3 1 2
```
改为：
```
1 2 3 4 5
4 3 1 2 3
```
改后最长公共子序列长度不变，而 $a$ 数组严格递增，所有公共子序列都是严格递增的，所以最长公共子序列长度就收数组 $b$ 的最长上升子序列长度，转为 LIS。
by Tomle @ 2024-04-27 18:22:13
改一下，令 $f_i$ 为 $a_{1 \sim i}$ 的 LIS 长度，则 $f_i=\max\limits_{j\lt i,a_j\lt a_i}\{f_j\}+1$
by Tomle @ 2024-04-27 18:23:51
@[Tomle](/user/942161) Orzorzorz已关
by I_like_play_eggy @ 2024-04-27 18:30:23
@[I_like_play_eggy](/user/1126325) LCS 也可以表示最长公共子串@$^&%#^&%*(（
by wukaichen888 @ 2024-04-27 18:31:29
@[wukaichen888](/user/723238) 那就要用 $\text{KMP}$ 算法，我也没学
by I_like_play_eggy @ 2024-04-27 18:35:25
@[I_like_play_eggy](/user/1126325) 是用 SAM 捏
by wukaichen888 @ 2024-04-27 18:58:46