数组中的最长山脉

暴力

将除过最后一个和第一个元素外都当作山顶进行遍历

class Solution {
    public int longestMountain(int[] A) {
        //1-n-1可以作为中心点
        int aSize = A.length; 
        int maxLen = 0;
        for(int mid=1;mid<aSize-1;mid++){
           int l = leftCnt(A,mid);
           int r = rightCnt(A,mid);
           if(l == 0 || r == 0) continue;
           maxLen = Math.max(maxLen,l+r+1);
        }
        return maxLen;
    }
    public int leftCnt(int []A,int mid){
        //mid
        int res = 0;
        for(int i=mid-1;i>=0;i--){
            if(A[i+1]>A[i]) res++; 
            else break;
        }
        return res;
    }
    public int rightCnt(int []A,int mid){
        int res = 0;
        for(int i=mid+1;i<A.length;i++){
            if(A[i-1]>A[i]) res++;
            else break;
        }
        return res;
    }

}

可以看出实际上是一个递增序列和递减序列和最大问题

class Solution {
    public int longestMountain(int[] a) {

        int aSize = a.length;
        if(aSize == 0) return 0;
        int[] dp = new int[aSize];//以a[i]为结束节点的递增序列长度
        int[] dp1 = new int[aSize]; //以a[i]为开始点的递减序列长度(倒序的结束点)
        Arrays.fill(dp,1);
        Arrays.fill(dp1,1);
        for(int i=1;i<aSize;i++){
            if(a[i] > a[i-1]) dp[i] = Math.max(dp[i-1]+1,dp[i]);
        }
        for(int i=aSize-2;i>=0;i--){
              if(a[i+1] < a[i]) dp1[i] = Math.max(dp1[i+1]+1,dp1[i]);
        }
        int res = 0;
        for(int i=1;i<aSize-1;i++){
            if(dp[i] < 2 || dp1[i] < 2) continue; 
            res = Math.max(res,dp[i]+dp1[i]);
        }
        return res == 0? 0:res-1;


    }
}