LeetCode 845 Longest Mountain in Array 正向DP+反向DP

You may recall that an array arr is a mountain array if and only if:

• arr.length >= 3
• There exists some index i (0-indexed) with 0 < i < arr.length - 1such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.

Solution

注意到这是连续的序列，所以只需要正向反向遍历更新一遍即可

class Solution {
private:
    int dp1[10003], dp2[10003];
    int ans=0;
public:
    int longestMountain(vector& arr) {
        int n = arr.size();
        for(int i=n-2;i>=0;i--){
            if(arr[i+1]