微信面试算法题-最长拼接子序列

面的微信部门，应用研发岗实习一面。我人都傻了，我填的不都是java研发之类的，怎么冒出个这么奇怪的岗位。

题目是这样子的：对于一个给定的子序列，比如说[1,2,3,10,4,2,5,6]，要求去除一段连续的数据，使得剩下的数据是非下降的。输出的结果是去除的最少数字的数量。（可以不唯一）

比如说对于上面这个序列，显然其去除的可以是10,4,2，也就是输出3。也可以选择去除3,10,4，结果也是相同的。

这道题是我面试腾讯微信部门的第二道面试题，感谢面试官给了我充足的时间，虽然我还是没有做出来QAQ。

当时的想法

提到这种上升或下降式的序列，第一个想到的就是最长连续上升子序列之类的题目，就想到用DP来做。然后发现一个很尴尬的问题：状态转移方程建不出来^_^。这个真的是从做DP到现在一直困扰我的梦靥了，那就没办法了。不排除能用DP做，只是我比较菜，有时间专门研究一下吧……

第二个想法就是观察原序列。显然，被去除掉的结构一定是存在逆序的，就是说索引顺序与值顺序不一致，比如10,4这样。那有一个想法，如果我用递归的思想，不断二分原序列，将其拆解到只剩下两个数字。然后对于小的逆序对，删除掉大的。再对其拼接的过程中不断去除逆序结构，最终应该会剩下多条顺序链。

但是在如何拼接顺序链以及确认该步骤是正确的地方上卡住了。

现在的想法

考完出来之后我就有了个新的想法。由于只能切一刀，显然只有三种情况：把前面部分切掉，只保留后面部分；把后面部分切掉，只保留前面部分；以及中间切一刀，保留两边部分。

无论怎么切，都可以用归纳法证明，剩下的一定是一条连续非下降子序列。所以问题转变为：求解以头开始或者以尾结束的最长连续子序列的长度，然后尝试把它们拼接起来。

算法正确性证明我忘了，好久没干了，不过感觉这个靠谱多了。