看到这个题，很明显会想到是两个“最长上升子序列”从左到右，从右到左各一遍，然后拼在一起即可。
关于最长上升子序列，普通解法是![图片说明](https://www.nowcoder.com/equation?tex=n%5E%7B2%7D "图片标题") 的时间复杂度
代码如下：

class Solution {
public:
    /**
     * 返回最大山峰序列长度
     * @param numberList int整型vector 给定的序列
     * @return int整型
     */
    int dp1[10005],dp2[10005];
    int mountainSequence(vector<int>& numberList) {
        // write code here
        int max1=-1,max2=0;
        int n = numberList.size();
        for(int i=0;i<n;i++)
         {
              dp1[i]=1;
              for(int j=0;j<i;j++)
              {
                   if(numberList[j]<numberList[i]) dp1[i]=max(dp1[i],dp1[j]+1);
              }
         }
         for(int i=n-1;i>=0;i--)
         {
              dp2[i]=1;
              for(int j=n-1;j>i;j--)
              {
                   if(numberList[i]>numberList[j]) dp2[i]=max(dp2[i],dp2[j]+1);
              }
         }
         //for(int i=0;i<n;i++) printf("%d ",dp2[i]);printf("\n");
         for(int i=0;i<n;i++)
         {
              max1=max(max1,dp1[i]+dp2[i]-1);
         }
         return max1;
    }
};

对于最长上升子序列，我们知道，有![图片说明](https://www.nowcoder.com/equation?tex=n%5Ctimes%20log_%7Bn%7D "图片标题")
那种二分的做法看下面代码，基本就是继承经典的那种二分求LIS，遍历每个元素的时候，记录当前维护的序列的长度，也就是以这个元素为结尾的元素的长度。然后倒着求一遍。

class Solution {
public:
    /**
     * 返回最大山峰序列长度
     * @param numberList int整型vector 给定的序列
     * @return int整型
     */
    int d[1000];
    int d1[1000];
    int d2[1000];
    int mountainSequence(vector<int>& numberList) {
        // write code here
        int n = numberList.size();
        memset(d,0,sizeof(d));
        memset(d1,0,sizeof(d1));
        memset(d2,0,sizeof(d2));
        int sum=0;
        for (int i=0; i<n; i++)
        {
            if(numberList[i]>d[sum]) {
                 d[++sum]=numberList[i];
            }
            else
            {
                int k=lower_bound(d,d+sum,numberList[i])-d;
                d[k]=numberList[i];
            }
            d1[i]=sum;
        }
        sum=0;
        for (int i=n-1; i>=0; i--)
        {
            if(numberList[i]>d[sum]) {
                d[++sum]=numberList[i];
            }
            else
            {
                int k=lower_bound(d,d+sum,numberList[i])-d;
                d[k]=numberList[i];
            }
            d2[i]=sum;
        }
        int sum1=0;
        for (int i=0; i<n; i++)
        {
            sum1=max(sum1,d1[i]+d2[i]-1);
        }
        return sum1;
    }
};

时间复杂度一下就降低了
下面这样写会更好一些

class Solution {
public:
    /**
     * 返回最大山峰序列长度
     * @param numberList int整型vector 给定的序列
     * @return int整型
     */
    int mountainSequence(vector<int>& numberList) {
        // write code here
        int n = numberList.size(), ret = 1;
        vector<int>left(n), right(n), dpl, dpr;
        for (int i = 0; i < n; i++)
        {
            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++)
            ret = max(ret, left[i] + right[i] - 1);
        return ret;
    }
};

由于这个题不想卡时间，所以前一种普通做法也能过的