一、动态规划

题目分析：

这题就是求一个序列，先升序后降序的序列，这个序列最长是多少？

就是找一个点，这个点左边的升序队列最长是多少？右边的降序队列最长是多少？

就是先求当前这个人左边的升序队列最长多少？然后同样的方法求右边的降序队列最长多少？

求左边最长升序思路：

这个问题就是给一个乱序的序列，找一个最长的升序队列。

那我们就从左到右、从1到n依次遍历这个序列，当遍历到第k个值时，它【左边的最长升序序列】是前面比它小的值的【左边的最长升序序列】加上1，因为当前第k个值要加上去了。

另外，因为要找一个最长的，所以需要遍历一下第k个值前面所有比它小的值，把他们的【左边的最长升序序列】+1，取最大的那个。得出的结果就是当前第k个值的【左边的最长升序序列】的长度值。

二、二分查找

这个思路大概如下：

首先还是转化成：给一个乱序的序列，求一个最长的升序（降序）子序列。

怎么求？

定义一个辅助数组。这个辅助数组的长度就最长升序子序列的长度。下面借助一个例子进行分析。

假设输入：1，3，6，4，7，10
1、输入1时辅助数组存的值是：【1】
2、输入3时辅助数组存的值是：【1、3】
3、输入6时辅助数组存的值是：【1、3，6】
4、输入4时辅助数组存的值是：【1、3，4】
5、输入7时辅助数组存的值是：【1、3，4，7】
6、输入10时辅助数组存的值是：【1、3，4，7，10】
结果为5。

当输入大于辅助数组最后一个值时，直接加到后面。

当输入不大于辅助数组最后一个值时，替换数组中离这个输入最近、且比它大的一个值

为什么？

只有当下一个升序子序列的长度大于上一个的升序子队列，最大的升序子序列才会增长。

比如：1、3、6、8、4、5、7中的1、3、6、8只有当1、3、4、5、7才可替换。前面1、3、4、5只是替换了1、3、6、8。

但是替换了并不会原本的8后面去接其它比它大的数值，因为8的位置替换成了5.