Longest Mountain Subarray

Posted: 22 Nov, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given an array of 'N' integers denoting the heights of the mountains. You need to find the length of the longest subarray which has the shape of a mountain.

A mountain subarray is defined as a subarray which consists of elements that are initially in ascending order until a peak element is reached and beyond the peak element all other elements of the subarray are in decreasing order.

Example:
If the given array is: [1 3 1 4]. The longest mountain subarray would be 3. This is because the longest mountain is  [1 3 1] having length 3.
Input Format:
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. 

Then the 'T' test cases follow.

The first line of each test case contains a single integer 'N' representing the length of the array.

The second line of each test case contains 'N' space-separated integers denoting the elements of the given array.
Output Format:
For each test case, print the length of the longest subarray which has the shape of a mountain in a seperate line.
Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
1 ≤ Ai ≤ 10^9

Time Limit : 1 sec 

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.
Approach 1
  • We generate all the possible subarrays by using two nested loops.
  • We can run two nested loops, the outer loop picks the starting element and the inner loop picks the ending element.
  • The third loop considers all elements in between the starting and ending elements.
  • Check if each subarray is a mountain or not. This can be done by checking if the subarray is first strictly increasing and then strictly decreasing.
  • Find its length, if it’s a mountain.
  • For all subarrays which are mountains, we take the length of the longest one.
Try Problem