题目描述

我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：

B.length >= 3
存在 0 < i < B.length - 1 使得 B[0] < B[1] < … B[i-1] < B[i] > B[i+1] > … > B[B.length - 1]
（注意：B 可以是 A 的任意子数组，包括整个数组 A。）

给出一个整数数组 A，返回最长 “山脉” 的长度。

如果不含有 “山脉” 则返回 0。

样例

示例 1：

输入：[2,1,4,7,3,2,5]
输出：5
解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。
示例 2：

输入：[2,2,2]
输出：0
解释：不含 “山脉”。
 

提示：

0 <= A.length <= 10000
0 <= A[i] <= 10000

算法1

(暴力枚举 or 最长连续上升子序列 + 最长连续下降子序列) $O(n^2)$

两重循环，找左边最小，右边最大能到的点

时间复杂度O（n ^ 2)

C++ 代码

class Solution {
public:
    int longestMountain(vector<int>& A) {
        //f[i]表示以i结尾的上升子序列,g[i]下降
        int res = 0;
        if(!A.size())return 0;
        int t = A[0];
        for(int m = 1 ; m < A.size();m++)
        {
            if(A[m] != t)
            {
                for(int i = 0 ; i < A.size(); i++)
                {
                    int j = i,k = i;
                    while(j-1 >= 0 && A[j] > A[j-1])j--;
                    while(k+1 < A.size() && A[k] > A[k+1])k++;
                    if(k == i || j == i)continue;
                    res = max(res,k-j+1);
                }
                return res;
            }
        }
        return 0;
    }
};