Reference: LeetCode

Difficulty: Medium

My Post: [Java] B-F, One-Pass, DP Solutions with Explanations (easy-understand)

## Problem

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.

**Note:**

- 0 <= A.length <= 10000
- Indicate that $O(N^2)$ is not okay.

- 0 <= A[i] <= 10000

**Example:**

1 | Input: [2,2,2] or [1,2,2] |

**Follow up:**

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

## Analysis

### Brute-Force

For an array of size $n$, we compute the mountain lengths for every subarray from size at least `3`

to `n`

.

**Note:** Be very careful about the index update.

1 | public int longestMountain(int[] A) { |

In terms of the mountain length calculation (the mountain should start from the first element), check out the examples in comments. The following code is similar to the one-pointer solution.

1 | private int mountainLen(int[] A, int lo, int hi) { |

**Time:** $O(N^3)$ (unacceptable)**Space:** $O(1)$

### One-Pass (one pointer)

By observation of the example below, we can actually go through the array and get the maximum mountain length in one pass.

1 | 0 1 2 3 4 5 6 7 8 9 10 |

In order to do that, we have to simulate the `going-up`

and `going-down`

processes in order. For example, while going up, the start point is at `1`

, the peek is at `3`

, and the end point is at `5`

. We cannot go further, so we have a mountain of length 5. We do that for the following mountain until we reach the end of the array.

The idea is not difficult, but the implementation is because of index manipulation and special/corner cases. Try to come up with some small examples and get some invariants.

**Note:**

- Since we check elements at
`A[i]`

and`A[i + 1]`

, the condition is`i < n - 1`

. - Record the starting point in each process, reconstruct a new mountain if
`i`

does not move at all (which means invalidity). - Go through your code for cases:
`[1,2,2]`

,`[2]`

,`[1,2,3]`

,`[3,2,1]`

.

1 | public int longestMountain(int[] A) { |

**Time:** $O(N)$**Space:** $O(1)$

### DP

Use extra two arrays `inc[]`

and `dec[]`

to store information we need and then go through the array.

**inc[i]**: The maximum increasing length for the subarray ending at`i`

. (constructed from left)- For example:
`[1,2,3]`

the`inc[i] = [0,1,2]`

.

- For example:
**dec[i]**: The maximum decreasing length for the subarray starting at`i`

. (constructed from right)- Both
`inc[]`

and`dec[]`

are initialized with $0$.

Then we go through the array from `1`

to `n - 1`

for each possible peak. We calculate the peak only when `inc[i]`

and `dec[i]`

are both non-zero.

**Note:** The length is `inc[i] + dec[i] + 1`

.

1 | // inc[] and inc[] are initialized with 0 |

Here is the code:

1 | public int longestMountain(int[] A) { |

**Time:** $O(N)$**Space:** $O(N)$