Longest Mountain Subarray Problem In C++

Hi guys, today we will try to solve one of the most asked problems in Competitive exams i.e. Longest Mountain Subarray Problem in C++.

Let us discuss the aim of the problem.

AIM: The program is to print the length of the longest mountain possible from the array provided.

The user has to enter the number of elements and an array as input.

Now, a question arises what is a mountain?

Mountain: A mountain is formed when the number increases and then decreases.

If the pattern initially decreases and then increases, it is called a valley.

APPROACH

So, before moving to the code, let us discuss the approach we are following.

We have to go through the complete array and search when 2 numbers are in increasing order. Once, we find the increasing order, we will store that index in some variable as a starting point. Now, we need to find at which position that order breaks. Because, after that position, the order starts either decreasing or remains constant. If the order remains constant, then we need to remove the starting index from our variable because it will not form any mountain.
For example, we have an array ={ 1,2,3,4,5,5,3,1}
when we find that the order remains constant i.e. 5 is coming after 5,
then we can not call it a mountain and hence we will remove the value of starting index.

But, if the order decreases, we have to find out till which position the order decreases and hence store that index in some another variable.

Longest Mountain Subarray Problem

Now, let us move to the code, you will understand it better.

#include <bits/stdc++.h>
using namespace std;
void LongestMountain(int a[], int n)
{
    int start=-1,finish=-1,len=0;
    if (n < 3)
    {
        cout<<"0";
        return;
    }
    for (int i=0;i<n-1;i++)
    {
        if(a[i+1]>a[i])
        {
            if (finish!= -1)
            {
                finish = -1;
                start = -1;
            }
            if (start == -1)
            {
                start = i;
            }
        }
        else
        {
            if (a[i + 1] < a[i])
            {
                if (start != -1)
                    finish = i + 1;
                if (finish != -1 && start != -1)
                {
                    if (len < finish-start + 1)
                        len = finish-start + 1;
                }
            }
            else
            {
                start = -1;
                finish = -1;
            }
        }
    }
    cout<<len;
}
int main()
{
    int arr[100],n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>arr[i];
    LongestMountain(arr,n);
    return 0;
}

In this code, I have used the same logic which I told earlier.

I have created an array arr that will store the elements. I also used another variable that will store the size of the array.
After declaring both of them, I asked the user to enter the size and then enter the elements of the array.
Then called the LongestMountain function, which will print the longest length of the mountain.

In the LongestMountain function, I have declared 3 variables start, finish, and len. ‘Start’ will store the starting index of the mountain, the ‘finish’ will store the last index of the mountain, and ‘len’ will store the length of the mountain.

I have used another important condition i.e. if the size of the array is less than 3 or if the array contains only 2 elements, then we can not form any mountain and hence will print 0.

After that, I am running a loop from the 0th index to the second last index and check the order of the number in the array.
If, it gets the increasing order then initialize the start variable with the index i and if, it gets the decreasing order, then initialize the finish variable with the index i+1. There can be another case, i.e. if it gets two same numbers then we will initialize start and finish with -1.
We will check, if the length of the current mountain is greater than the length stored in the len variable then we will update the value of ‘len’ with this new value.

This process continues until the whole array gets checked.

At last, it will display the length of the longest mountain.

Let us take an example, consider the input entered by the user:

10
1 3 5 7 9 4 2 0 1 0

In this example, we are having 2 mountains i.e. first from index 0 to index 7 and the other one from index 7 to index 9. But the program should print the longest mountain so it will display the length of the first mountain i.e. 8

Output:

8

So, in this article, we learned about the longest mountain subarray problem in the C++ language. You can practice more questions based on the subarray. Smallest subarray with k distinct numbers

Leave a Reply

Your email address will not be published. Required fields are marked *