题意

给定数组。

找一个子序列，满足先严格递增后严格递减，求最大的子序列长度

数组长度 $\le 1000\backslash leq\; 1000$≤1000

方法

dfs(TLE)

我们枚举每一个位置，假设这个位置是顶点，从这个顶点向两侧深度搜索。

搜索的设计为，遍历点。

如果一个点可选，则考虑选择改点并继续深搜，深搜返回后遍历继续，也可以不选择该点，遍历继续。

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回最大山峰序列长度
# @param numberList int整型一维数组 给定的序列
# @return int整型
#
class Solution:
    # 深度搜索，变化的内容是：上一次的值，下标，搜索方向
    def dfs(self, numberList, lastVal, idx, di):
        ans = 0
        i = idx
        while not (i == len(numberList) or i < 0): # 搜索边界控制
            if (numberList[i] - lastVal) < 0: # 严格小于并选取该值
                ans = max(ans,1+self.dfs(numberList, numberList[i],i+di,di)) # 递归搜索 下一个位置并更新 上一次的值和搜索的起始下标
            i+=di
        print(lastVal,idx,di,ans)
        return ans
    
    def mountainSequence(self , numberList ):
        ans = 1
        for i in range(len(numberList)): # 枚举所有位置为峰值, 从这个位置向左右两侧搜最大的长度
            ans = max(ans, self.dfs(numberList, numberList[i], i+1, 1)+self.dfs(numberList, numberList[i], i-1, -1)+1)
        return ans

复杂度分析

时间复杂度: 如果原始数组自身就是满足题意的，那么我们在搜顶点时，就相当于枚举了所有可行的选择，所以时间复杂度最坏能到$O\left(2^n\right)O(2^n)$O(2n)

空间复杂度: 我们主要空间使用是递归调用，其栈空间与最大深度有关，所以空间复杂度$O\left(n\right)O(n)$O(n)

动态规划

假设我们仅需要求单调递增子序列

那么遍历数组，并且分别记录长度为1，为2，为3,...对应的最小结尾值。

那么遍历过程中，我们可以计算出每一个位置对应的最大长度。

以示例1为例。[1,2,3,6,1]

初始化，不同长度的最小值

第一个值为1，当前所有为空，则放在长度1，并且说明第一个值最大的严格单调递增长度为1

第二个值为2，当前最大的为1，所以放在长度2，并且说明第二个值最大的严格单调递增长度为2

第三个值为3，当前最大的为2，所以放在长度3，并且说明第三个值最大的严格单调递增长度为3

第四个值为6，当前最大的为3，所以放在长度4，并且说明第四个值最大的严格单调递增长度为4

第五个值为1，当前首个值也为1，所以放在长度1，并且说明第五个值最大的严格单调递增长度为1

综上通过上面的步骤，我们通过一个辅助的数组,得到了从头开始每个位置的最大严格单调递增长度。

那么对于 递减的部分，仅需要把数组翻转，再求一次最大单调递增长度。

最后，对于数组的每一个位置，计算其 最大严格单调递增长度+最大严格单调递减长度 即可。这样便能求得最大值

代码

class Solution {
public:
    vector<int> getLongest(vector<int> & arr){ // 获取从头到每个位置的最大单调递增的长度
        vector<int> idx2len(arr.size(),0); // 结果数组 [位置] = 长度
        vector<int> rank = {}; // 辅助数组 当前不同最大长度的最小值
        for(int i = 0;i<arr.size();i++){
            int item = arr[i];
            if(i == 0){
                idx2len[i] = 1;
                rank.push_back(item);
                continue;
            }
            if( (item - rank[0])  <= 0){ // 不大于第一个元素 ，则长度为1的最小值更新
                idx2len[i] = 1;
                rank[0] = item;
                continue;
            }
            if( (item - rank[rank.size()-1])  > 0){ // 比最后一个还大，则长度+1
                rank.push_back(item);
                idx2len[i] = rank.size();
                continue;
            }
            // 其它中间的情况
            int l = 0 ;
            int r = rank.size() -1 ; 
            // 二分查找 满足的位置 rank[l] < item <= rank[r]
            while(l+1<r){
                int m = (l+r)/2;
                if((item-rank[m]) > 0){
                    l = m;
                }else{
                    r = m;
                }
            }
            idx2len[i] = r+1; // 记录当前长度
            rank[r] = item;
        }
        return idx2len;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最大山峰序列长度
     * @param numberList int整型vector 给定的序列
     * @return int整型
     */
    int mountainSequence(vector<int>& numberList) {
        vector<int> inc = getLongest(numberList); 
        reverse(numberList.begin(),numberList.end()); // 倒序后，可以用同样的方法求单调递减
        vector<int> dec = getLongest(numberList);
        int ans = 1;
        for(int i = 0;i < numberList.size();i++){ // 枚举每个位置为峰值，找最大的左右长度和
            ans = max(ans,inc[i]+dec[numberList.size()-1-i]-1);
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 我们计算了两次 最大单调递增长度$O(n\cdot log(n\left)\right)O(n\; \backslash cdot\; log(n))$O(n⋅log(n))，进行了一次数组翻转$O\left(n\right)O(n)$O(n)，和一次最大值计算$O\left(n\right)O(n)$O(n)。因此总时间复杂度为$O(n\cdot log(n\left)\right)O(n\; \backslash cdot\; log(n))$O(n⋅log(n))

空间复杂度: 我们在 计算最大单调递增是用了一个辅助的rank数组，和一个结果数组，这两个数组都是和原数组长度相关。因此总空间复杂度为O(n)