算法思想一：动态规划+两次遍历

解题思路：

最长上升子序列的衍生题，所谓最长凸子序列

从左边到峰顶的序列是从左到右的最长上升子序列，从峰顶到右侧的序列是从右到左的最长上升子序列

因此可以采用从左到右计算一次各个子序列的最长上升子序列 l2r（其中l2r[i]表示以i结束的最长上升子序列长度），从右到左计算一次各个子序列的最长上升子序列 r2l，将对应位置的解相加，取最大

注：结果要减去1，因为峰顶包含了2次。

图解：

代码展示：

Python版本 

class Solution:
    def mountainSequence(self , numberList ):
        # write code here
        # 左右两个最长上升子序列l2r, r2l
        l2r, r2l = [1], [1]
        # 正序计算从左到右的最长上升子序列l2r
        for i in range(1,len(numberList)):
            temp = 1
            for j in range(len(l2r)):
                if numberList[i] > numberList[j]:
                    temp = max(temp,l2r[j]+1)
            l2r.append(temp)
        # 倒序计算从右到左的最长上升子序列r2l
        for i in range(len(numberList)-2,-1,-1):
            temp = 1
            for j in range(len(r2l)):
                if numberList[i] > numberList[-1-j]:
                    temp = max(temp,r2l[j]+1)
            r2l.append(temp)
        result = 0
        # 将 l2r, r2l 相加减去1，去除峰顶
        for i in range(len(l2r)):
            result = max(result, l2r[i] + r2l[-1-i] - 1)
        return result

复杂度分析

时间复杂度：N表示数组的长度，从左到右/从右到左计算最长上升子序列都需要时间

空间复杂度：l2r，r2l数组占用空间

算法思想二：动态规划+二分

解题思路：

方法一的时间复杂度较高，因此可以采用二分法实现从左到右最长上升子序列计算、从右到左最长上升子序列计算

1、定义, 分别表示从左到右最长上升子序列长度、从右到左最长上升子序列长度

2、继承经典的二分求LIS，遍历每个元素的时候，记录当前维护的序列的长度，也就是以这个元素为结尾的元素的长度，然后倒着求一遍

3、最后将left right将对应的位置相加，再减去一个山峰的数量（取最大值）

代码展示：

C++版本 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最大山峰序列长度
     * @param numberList int整型vector 给定的序列
     * @return int整型
     */
    int mountainSequence(vector<int>& numberList) {
        // write code here
        // 初始化
        int n = numberList.size(), ret = 1;
        // 从左边最长递增子序列left(n)， 从右边最长递增子序列 right(n)
        // dpl, dpr 辅助数组
        vector<int>left(n), right(n), dpl, dpr;
        // 一次遍历 
        for (int i = 0; i < n; i++)
        {
            // lower_bound 二分查找函数
            // 正向
            auto itl = lower_bound(dpl.begin(), dpl.end(), numberList[i]);
            // 反向
            auto itr = lower_bound(dpr.begin(), dpr.end(), numberList[n - 1 - i]);
            // 正向遍历判别
            if (itl == dpl.end()) dpl.push_back(numberList[i]);
            else *itl = numberList[i];
            // 反向遍历判别
            if (itr == dpr.end()) dpr.push_back(numberList[n - 1 - i]);
            else *itr = numberList[n - 1 - i];
            left[i] = dpl.size();
            right[n - 1 - i] = dpr.size();
        }
        // 最后循环更新最大值
        for (int i = 0; i < n; i++)
            // left right将对应的位置相加，再减去一个山峰的数量（取最大值）
            ret = max(ret, left[i] + right[i] - 1);
        return ret;
    }
};

复杂度分析

时间复杂度：N表示数组的长度，最外层遍历时间，内层二分计算时间

空间复杂度：left，right占用空间