6Companies30days

Longest Mountain

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 - 1 such 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.

Example

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

Solution

• Find length of increase
• Find length of decrement
• MaxHeight = max( maxHeight, inc+dec+1)
• Be carefull when equal numbers are present, do i++

    int longestMountain(vector<int>& nums) {
		
	int maxMountain = 0 ;
	int i = 0 ;
	while( i+1 < nums.size()){

		int inc = 0 , dec = 0;
		while( i+1 < nums.size() and  nums[i+1] > nums[i] ){
			inc++;
			i++;
		}
		while( i+1 < nums.size() and nums[i+1] < nums[i] ){
			dec++;
			i++;
		}
		// cout<<i<<" "<<inc<<" "<<dec<<endl;
		if( inc > 0  and dec > 0 ) {
			maxMountain = max(maxMountain, inc+dec+1);
		}
		if( inc == 0 and dec == 0 ){
			i++;
		}

	}
	
	return maxMountain;
    }