Overview

Given consecutive points, find the length of the longest interval where the elevation difference between adjacent points is at most \(K\).

Analysis

In this problem, a “stable hiking interval” refers to a consecutive sequence of points where the elevation difference between every pair of adjacent points is at most \(K\). For example, if the elevations are [10, 15, 18, 25] and \(K=7\), then [10, 15, 18] is a stable interval since all elevation differences are at most \(7\), but since the difference between 18 and 25 exceeds \(7\), [10, 15, 18, 25] is not a stable interval.

A naive approach would be to enumerate all intervals and check whether each satisfies the condition, but this would be \(O(N^3)\) or \(O(N^2)\), which is too slow for the constraint \(N \leq 2 \times 10^5\).

Instead, we exploit the property that the interval must be consecutive and that once the condition is violated, everything beyond that point is invalid. This leads to a two-pointer (sliding window) style approach. That is, rather than fixing the left endpoint, we extend the current stable interval as far as possible, and when the condition is violated, we simply start a new interval.

With this approach, each element is examined at most once, so the overall time complexity is \(O(N)\).

Algorithm

The solution proceeds as follows:

1. Maintain the length of the current stable interval current_length, initialized to 1 (a single point is always a stable interval).
2. Scan from left to right, checking the elevation difference between adjacent points:
   • If the difference is at most \(K\), increment current_length and update the maximum length.
   • If the difference exceeds \(K\), the stable interval is broken, so reset current_length to 1.
3. Output the length of the longest interval found.

In this way, we can efficiently examine all consecutive intervals.

Example

Input:

5 3
10 12 15 16 20

Processing flow: - Point 1→2: |10-12|=2 → OK → current_length = 2 - Point 2→3: |12-15|=3 → OK → current_length = 3 - Point 3→4: |15-16|=1 → OK → current_length = 4 - Point 4→5: |16-20|=4 → NG → interval reset, current_length = 1

The maximum length is 4.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding the input array)

Implementation Notes

• When \(N = 1\), the interval length is always 1, so it’s safe to handle this as a special case at the beginning.

• Don’t forget to reset current_length to 1 when the condition is violated.

• Update the maximum value only when the condition is satisfied.

  Source Code

N, K = map(int, input().split())
A = list(map(int, input().split()))

if N == 1:
    print(1)
else:
    max_length = 1
    current_length = 1

    for i in range(N - 1):
        if abs(A[i] - A[i + 1]) <= K:
            current_length += 1
            if current_length > max_length:
                max_length = current_length
        else:
            current_length = 1

    print(max_length)

---

This editorial was generated by qwen3-coder-480b.