Overview

This problem asks us to find the maximum length of a contiguous interval of \(N\) mountains lined up from east to west that is “mountain-shaped” (strictly increasing and then strictly decreasing) and satisfies the condition that “the difference between the maximum and minimum elevations is at least \(K\)”.

Analysis

1. Naive Approach and Its Limitations

Let’s consider a brute-force search over all intervals \([l, r]\) (\(1 \le l \le r \le N\)). There are \(O(N^2)\) possible intervals. For each interval, determining whether it is “mountain-shaped” and whether “the difference between the maximum and minimum values is at least \(K\)” takes \(O(N)\) time. This results in a total time complexity of \(O(N^3)\) (or \(O(N^2)\) with optimization). Since the constraint in this problem is \(N \le 10^6\), this approach will result in a Time Limit Exceeded (TLE) error.

2. Fixing the “Peak” Approach

A mountain-shaped interval must have a “peak” where the elevation is maximized. Therefore, we can consider how far we can expand the interval to the left and right when we fix each position \(i\) as the peak (the position with the maximum elevation).

Let \([L[i], R[i]]\) be the maximum mountain-shaped interval with position \(i\) as the peak. * Left direction (strictly increasing part): Let \(L[i]\) be the leftmost index from \(i\) to the left where the elevation continues to decrease (i.e., gets lower as we go left). In other words, \(H_{L[i]} < H_{L[i]+1} < \cdots < H_i\) holds. * Right direction (strictly decreasing part): Let \(R[i]\) be the rightmost index from \(i\) to the right where the elevation continues to decrease (i.e., gets lower as we go right). In other words, \(H_i > H_{i+1} > \cdots > H_{R[i]}\) holds.

With this definition, the largest mountain-shaped interval containing peak \(i\) is \([L[i], R[i]]\).

3. Simplifying the “Elevation Difference of at least \(K\)” Condition

In the interval \([L[i], R[i]]\), where are the maximum and minimum elevations? * Maximum value: Since \(i\) is the peak, it is clearly \(H_i\). * Minimum value: Since the elevation decreases as we go towards the left end and also as we go towards the right end, the minimum value must be at one of the two endpoints of the interval, which is \(\min(H_{L[i]}, H_{R[i]})\).

Therefore, the condition “the difference between the maximum and minimum values in this interval is at least \(K\)” can be rewritten as follows:

\[H_i - \min(H_{L[i]}, H_{R[i]}) \ge K\]

This is equivalent to:

\[H_i - H_{L[i]} \ge K \quad \text{or} \quad H_i - H_{R[i]} \ge K\]

If this condition is met, the interval \([L[i], R[i]]\) becomes a valid candidate. Its length is \(R[i] - L[i] + 1\).

4. Fast Computation of \(L[i]\) and \(R[i]\) (Dynamic Programming)

Calculating \(L[i]\) and \(R[i]\) naively for each \(i\) would take \(O(N^2)\) time in total. However, by utilizing the relationship between adjacent elements (a dynamic programming-like approach), we can compute each of them in \(O(N)\) time.

• How to find \(L[i]\) (computed from left to right):

  • When \(H[i-1] < H[i]\), the increasing trend from peak \(i\) to the left can inherit the trend of \(i-1\). Thus, \(L[i] = L[i-1]\).
  • Otherwise (when \(H[i-1] \ge H[i]\)), the mountain to the left is higher than or equal to the current one, so we cannot extend to the left. Thus, \(L[i] = i\).

• How to find \(R[i]\) (computed from right to left):

  • When \(H[i] > H[i+1]\), the decreasing trend from peak \(i\) to the right can inherit the trend of \(i+1\). Thus, \(R[i] = R[i+1]\).
  • Otherwise (when \(H[i] \le H[i+1]\)), the mountain to the right is higher than or equal to the current one, so we cannot extend to the right. Thus, \(R[i] = i\).

By doing this, we can precompute \(L[i]\) and \(R[i]\) for all \(i\) in \(O(N)\) time.

---

Algorithm

1. Constructing Array \(L\)

   • Set \(L[0] = 0\).
   • For \(i\) from \(1\) to \(N-1\) in order: if \(H[i-1] < H[i]\), set \(L[i] = L[i-1]\); otherwise, set \(L[i] = i\).

2. Constructing Array \(R\)

   • Set \(R[N-1] = N-1\).
   • For \(i\) from \(N-2\) down to \(0\) in reverse order: if \(H[i] > H[i+1]\), set \(R[i] = R[i+1]\); otherwise, set \(R[i] = i\).

3. Updating the Maximum Value

   • For each \(i\) (\(0 \le i < N\)), check if the condition \(H[i] - H[L[i]] \ge K\) or \(H[i] - H[R[i]] \ge K\) is satisfied.
   • If it is satisfied, update the answer (maximum length) with the interval length \(R[i] - L[i] + 1\).

---

Complexity

• Time Complexity: \(O(N)\) It takes \(O(N)\) to construct the array \(L\), \(O(N)\) to construct the array \(R\), and \(O(N)\) to perform the condition checks and update the maximum value for each \(i\). Therefore, the overall time complexity is \(O(N)\), which runs extremely fast and easily passes within the time limit even for \(N = 10^6\).
• Space Complexity: \(O(N)\) We use \(O(N)\) memory to store the input elevation array \(H\) and the left/right boundary index arrays \(L\) and \(R\).

---

Implementation Points

• Transition in 1D Arrays: When finding \(L[i]\) or \(R[i]\), we only refer to the information of the immediately preceding (or succeeding) element, so it can be implemented with simple loops.

• Be Careful with Boundary Conditions: When computing \(R\), we need to loop in reverse order starting from the right end (\(N-1\)). Be careful to avoid out-of-bounds index access.

• Fast I/O: In Python, since the number of inputs is large, using sys.stdin.read to read all inputs at once reduces the overhead caused by I/O operations.

  Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    H = [int(x) for x in data[2:]]

    L = [0] * N
    for i in range(1, N):
        if H[i - 1] < H[i]:
            L[i] = L[i - 1]
        else:
            L[i] = i

    R = [0] * N
    R[N - 1] = N - 1
    for i in range(N - 2, -1, -1):
        if H[i] > H[i + 1]:
            R[i] = R[i + 1]
        else:
            R[i] = i

    ans = 0
    for i in range(N):
        if H[i] - H[L[i]] >= K or H[i] - H[R[i]] >= K:
            length = R[i] - L[i] + 1
            if length > ans:
                ans = length

    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-high.