上周在一次采访中，我被问到了上面的问题，正如预期的那样，我没能正确回答，后来当我检查时，我发现这是一个基于动态规划的算法我不精通动态编程，但假设我要设计这个算法，那么我应该如何处理它？
假设，我从其他分而治之的算法（如MergeSort）中汲取灵感，并设计如下解决方案：
把这个序列分成两半。
求两半中增长最长的子序列
把两半连接起来。
很明显有一些丢失的碎片，但是怎么从这里往前走呢？
最佳答案
你的建议行不通，因为两个半部中最长的序列通常不会是连续的，当你加入一半时，可能存在更长的序列。
您可以按如下方式解决此问题：
在两半中，找出最长的递增子序列，让l和r；
在两半中，找出最长的左对齐递增子序列，让LL和RL；
在两半中，找出最长的递增子序列，使lr和rr右对齐；
如果L，R，LR+RL形成一个递增序列，则保持L，R，LR+RL的最长；
对于左对齐的子序列，如果形成递增的子序列，则保持LL或整个左子序列+RL；
对于右对齐的子序列，如果形成递增子序列，则保留rr或lr+整个右子序列。
所有这些操作都在一个递归过程中完成。当您将两个子序列连接起来时，检查它们是否形成一个递增的子序列只需要比较面向元素。