使用分而治之找到最长的递增子序列
Finding longest increasing sub-sequence using divide and conquer
上周在面试中被问到上面的问题，果然没能答对，后来查了一下发现是基于动态规划的算法。我不精通动态规划，但假设我要设计这个算法，我应该如何处理它？
假设，我从 MergeSort 等其他分而治之的算法中汲取灵感，并设计如下解决方案：
- 将序列分成两等份。
- 求两半中最长的递增子序列
- 加入两半。
明明是缺了一块，怎么从这里往前走？
你的建议行不通，因为两半中最长的序列通常不会连续，当你加入两半时可能存在更长的序列。
您可以按如下方式解决此问题：
两半求最长的递增子序列，设L和R；
在两半中，找到左对齐的最长递增子序列，让LL和RL；
两半求右对齐的最长递增子序列，设LR和RR；
最长的，如果L,R,LR+RL后者构成递增序列，则保持最长；
对于左对齐，如果形成递增子序列，则保留LL或整个左子序列+RL；
对于右对齐，如果形成递增子序列，则保留RR或LR+整个右子序列
所有这些操作都是在一个递归过程中完成的。当你连接两个子序列时，检查它们是否形成一个递增的子序列只需要比较面对的元素。
更新：
这个“修复”没有经过彻底检查。
上周在面试中被问到上面的问题，果然没能答对，后来查了一下发现是基于动态规划的算法。我不精通动态规划，但假设我要设计这个算法，我应该如何处理它？
假设，我从 MergeSort 等其他分而治之的算法中汲取灵感，并设计如下解决方案：
- 将序列分成两等份。
- 求两半中最长的递增子序列
- 加入两半。
明明是缺了一块，怎么从这里往前走？
你的建议行不通，因为两半中最长的序列通常不会连续，当你加入两半时可能存在更长的序列。
您可以按如下方式解决此问题：
两半求最长的递增子序列，设L和R；
在两半中，找到左对齐的最长递增子序列，让LL和RL；
两半求右对齐的最长递增子序列，设LR和RR；
最长的，如果L,R,LR+RL后者构成递增序列，则保持最长；
对于左对齐，如果形成递增子序列，则保留LL或整个左子序列+RL；
对于右对齐，如果形成递增子序列，则保留RR或LR+整个右子序列
所有这些操作都是在一个递归过程中完成的。当你连接两个子序列时，检查它们是否形成一个递增的子序列只需要比较面对的元素。
更新：
这个“修复”没有经过彻底检查。