最长公共子序列|最长公共子串|最长重复子串|最长不重复子串|最长回文子串|最长递增子序列|最大子数组和

2012年6月27日Yx.Ac发表评论阅读评论文章作者：Yx.Ac 文章来源：勇幸|Thinking (http://www.ahathinking.com) 转载请注明，谢谢合作。

---

最近练手，整理了一个“最”系列的主题，这些题目有点绕，个别的还有别名（详见博文），混在一块比较乱，就索性放在一起做了个整理，区别的时候要注意子序列与子串的不同，前者不要求连续，后者要求连续；由于大部分跟DP有关，有的还可以渐进寻求多种解法，可以用来做不错的练手。

下面是这些问题的博文目录

==========================

==========================

总结：

问题分类
- 前两个是关于两个字符串的问题、中间三个是关于单个字符串的问题，最后两个是数组相关的问题；不过不一定绝对，例如最长公共子序列也可以是数组问题；
- 从解决方案看，12属于“二维”DP问题，因为是两个对象间的问题；467属于“一维”DP问题，是单个对象的问题；345又是后缀数组的典型应用。
为练手，对大多数问题，尽量逐步探索，整理了多种思路，例如在最长不重复子串问题中，我逐步优化，尝试了四种实现方法，并成功得到了时间为O(N)，辅助空间为常数的方案，回头反思，发现其优化的思维得益于对最大子数组和以及LIS的整理与思考。
这些问题之间相互有很多相通的地方，例如，在最长不重复子串问题中，其DP思路与最长递增子序列有点类似，二者同属“一维”的问题，并且都需要记录当前元素“之前”的某些信息；而在DP优化过程中，最长不重复子串问题又与最大子数组和的优化同出一辙，这两个“一维”的DP问题都只使用O(1)的空间便可以记录子问题的最优解，这种“便捷”的方案并不是空穴来风，而是先通过“规规矩矩”的DP一步步探索，才发现这种“trick”的存在，很是有意思。

勘误：

本系列文章所有代码出现 char xx [256] 的地方改为 int xx [256] ，因为从逻辑上讲char xx[256] 是有可能出问题的。（感谢HFC）

本节相关代码可以到这里下载。

（全文完）

秒客网