LeetCode [845] Longest Mountain in Array

 845. Longest Mountain in Array

Medium

Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:

• B.length >= 3
• There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain. 

Return 0 if there is no mountain.

Example 1:

Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: [2,2,2]
Output: 0
Explanation: There is no mountain.

Note:

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

Follow up:

• Can you solve it using only one pass?
• Can you solve it in O(1) space?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public int longestMountain(int[] A) { int n = A.length; int[] dp1 = new int[n]; int[] dp2 = new int[n]; for(int i=1; i<n; ++i){ if(A[i]>A[i-1]){ dp1[i] = dp1[i-1]+1; } } for(int i=n-2; i>=0; --i){ if(A[i]>A[i+1]){ dp2[i] = dp2[i+1]+1; } } int r = 0; for(int i=1; i<n-1; ++i){ if(dp1[i]>0 && dp2[i]>0){ int t = dp1[i] + dp2[i] + 1; r = Math.max(r, t); } } return r; } }

1 2 3 4 5 6 7 8 9 10 11 12

class Solution { public int longestMountain(int[] A) { int res = 0, up = 0, down = 0; for (int i = 1; i < A.length; ++i) { if (down > 0 && A[i - 1] < A[i] || A[i - 1] == A[i]) up = down = 0; if (A[i - 1] < A[i]) up++; if (A[i - 1] > A[i]) down++; if (up > 0 && down > 0 && up + down + 1 > res) res = up + down + 1; } return res; } }