CodingGyan

Longest Mountain in an Array

hard Arrays

Problem

A mountain is a part of the array (consecutive numbers) of length at least 3 that goes strictly up to a peak and then strictly down. Print the length of the longest mountain, or 0 if there is none.

Constraints

  • 1 <= n <= 10^5
  • |a[i]| <= 10^9

Examples

Input

7
2 1 4 7 3 2 5

Output

5

Solutions

Best approachTime O(n)Space O(1)

At every peak we measure the slope to the left and to the right. After a mountain we jump to its end, so each number is read at most twice. The total time is O(n) with O(1) memory.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Longest mountain.
 * Input   : n, then n integers.
 * Output  : The length.
 * Approach: Peak and jump.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(int[] a) {
        int best = 0;
        int i = 1;
        while (i < a.length - 1) {
            // Step 1: Look for a peak: a number bigger than both neighbours.
            if (a[i - 1] < a[i] && a[i] > a[i + 1]) {
                // Step 2: Walk left while the numbers go down, and right while they go down.
                int left = i;
                int right = i;
                while (left > 0 && a[left - 1] < a[left]) {
                    left--;
                }
                while (right < a.length - 1 && a[right] > a[right + 1]) {
                    right++;
                }
                best = Math.max(best, right - left + 1);
                // Step 3: The next mountain can start only after this one, so jump to its end.
                i = right;
            } else {
                i++;
            }
        }
        return best;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(solve(a));
    }
}
Hints (2)
  1. What is a peak?
  2. Why can we jump to the end of the mountain?

Try these next