Overview

Considering each peak as the “summit of a mountain shape”, this problem asks us to find the longest interval centered at this summit that is strictly monotonically increasing to the left and strictly monotonically decreasing to the right. Among all such intervals with an elevation difference of at least \(K\), we need to find the maximum number of peaks (i.e., the maximum interval length).

Analysis

A naive approach would be to check all intervals \([l, r]\) and determine if they form a mountain shape and have an elevation difference of at least \(K\). However, there are \(O(N^2)\) intervals, which is far too slow for \(N \leq 10^6\).

Here, we make an important observation: any mountain-shaped interval must have a single peak \(k\) as its “summit”. Thus, we can fix the summit and analyze the problem.

When the summit \(k\) is fixed:

• To the left of the summit, we can extend to the left as long as the sequence is strictly monotonically increasing (\(H_l < H_{l+1} < \cdots < H_k\)).
• To the right of the summit, we can extend to the right as long as the sequence is strictly monotonically decreasing (\(H_k > H_{k+1} > \cdots > H_r\)).

The “maximum mountain-shaped interval centered at summit \(k\)” obtained this way is the best candidate for summit \(k\). The reason is as follows:

In any mountain-shaped interval containing summit \(k\):

• The maximum value is always \(H_k\) (the summit).
• The minimum value is the smaller of the two endpoints, \(H_l\) and \(H_r\) (since the left side increases towards the summit and the right side decreases away from it, the endpoints are the lowest points).

Since extending the interval as much as possible decreases (or keeps constant) the elevations at both endpoints, the elevation difference \(H_k - \min(H_l, H_r)\) is maximized. Furthermore, the length of the interval is also maximized. This means that “if the maximum possible interval has an elevation difference of less than \(K\), then any shorter sub-interval will also fail to satisfy the condition.” Therefore, it is sufficient to check only the maximum mountain-shaped interval for each summit.

Algorithm

We can use a standard technique to precompute the lengths of contiguous subsequences.

• \(\text{up}[i]\): The length of the strictly monotonically increasing sequence ending at peak \(i\).
  • If \(H_{i-1} < H_i\), then \(\text{up}[i] = \text{up}[i-1] + 1\). Otherwise, \(\text{up}[i] = 1\).
• \(\text{down}[i]\): The length of the strictly monotonically decreasing sequence starting at peak \(i\).
  • If \(H_i > H_{i+1}\), then \(\text{down}[i] = \text{down}[i+1] + 1\). Otherwise, \(\text{down}[i] = 1\).

Using these, the maximum mountain-shaped interval with peak \(i\) as the summit can be represented as:

• Left endpoint: \(l = i - \text{up}[i] + 1\)
• Right endpoint: \(r = i + \text{down}[i] - 1\)
• Length: \(\text{up}[i] + \text{down}[i] - 1\) (we subtract \(1\) because the summit is double-counted)

For each \(i\), if the difference between the maximum value \(H_i\) and the minimum value \(\min(H_l, H_r)\) is at least \(K\), we update our answer with this length.

Example: Consider \(H = [1, 3, 5, 2, 4]\) and \(K = 3\).

• When \(i=2\) (value \(5\), using 0-based indexing) is the summit, it extends to the left as \(1, 3, 5\) (increasing) and to the right as \(5, 2\) (decreasing). Thus, the interval is \([1, 3, 5, 2]\) of length \(4\). The maximum value is \(5\), the endpoints are \(1\) and \(2\) (so the minimum is \(1\)), and the difference is \(4 \geq 3\), which satisfies the condition.

In this way, we can evaluate each summit in \(O(1)\) time.

Complexity

• Time Complexity: \(O(N)\) (both precomputation and scanning are linear)
• Space Complexity: \(O(N)\) (for arrays \(H\), \(\text{up}\), and \(\text{down}\))

Implementation Details

• The definition of the mountain shape uses strict inequalities. Note that the increasing/decreasing sequence is interrupted (reset to length \(1\)) at points where \(H_i = H_{i+1}\). Allowing equality will result in WA (Wrong Answer).

• To find the minimum value in the interval, it is sufficient to take the smaller of the two endpoints (since the sequence increases towards the summit and decreases away from it, the endpoints are guaranteed to be the lowest points). There is no need to query the minimum of the entire interval.

• Since \(N\) can be as large as \(10^6\), reading the entire input at once using sys.stdin.buffer.read() (in Python) is recommended for fast I/O.

• An interval of length \(1\) (a single peak) is also technically a mountain shape, but its elevation difference is \(0\). Under the constraint \(K \geq 1\), this will never satisfy the condition. If no valid candidate is found, the initial value of \(0\) should be output.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    H = [int(x) for x in data[2:2+n]]

    up = [1] * n
    for i in range(1, n):
        if H[i-1] < H[i]:
            up[i] = up[i-1] + 1

    down = [1] * n
    for i in range(n-2, -1, -1):
        if H[i] > H[i+1]:
            down[i] = down[i+1] + 1

    ans = 0
    for i in range(n):
        l = i - up[i] + 1
        r = i + down[i] - 1
        hl = H[l]
        hr = H[r]
        mn = hl if hl < hr else hr
        if H[i] - mn >= k:
            length = up[i] + down[i] - 1
            if length > ans:
                ans = length

    print(ans)

main()

---

This editorial was generated by claude4.8opus-high.