Overview

Among “contiguous intervals” where the elevation difference between adjacent points is always at most \(K\), find the length (number of points) of the longest one.

Analysis

The condition for a stable hiking interval is “for all adjacent pairs \((A_k, A_{k+1})\) within the interval, \(|A_k-A_{k+1}|\le K\).”
In other words, an interval breaks only when there is a “break point” where even one pair satisfies \(|A_i-A_{i+1}|>K\).

The key observations are as follows:

• A portion where \(|A_i-A_{i+1}|\le K\) holds consecutively forms a stable interval in its entirety
• The moment \(|A_i-A_{i+1}|>K\) appears, the interval is split at that point

A naive approach such as “checking stability for all pairs \((i,j)\)” would involve \(O(N^2)\) intervals, and verifying each could take additional time, leading to worst-case \(O(N^3)\). This is far too slow for \(N\le 2\times 10^5\).

Instead, we can solve this with a single pass: scan from left to right, extending the current consecutive length as long as the condition is satisfied, and resetting when a break point is encountered.

Example: \(K=3\), \(A=[10,12,14,20,22]\)
The differences are \(2,2,6,2\), so the third difference \(6>3\) is a break point.
The stable intervals are \([10,12,14]\) (length 3) and \([20,22]\) (length 2), so the answer is 3.

Algorithm

1. Let cur be “the length of the current stable interval” and best be “the maximum length” (both initialized to 1).
2. For \(i=1\) to \(N-1\) (or \(0\) to \(N-2\) in 0-indexed) in order:
   • If \(|A_i-A_{i+1}|\le K\), then cur += 1 (extend the interval)
   • Otherwise (break point):
     Update best = max(best, cur), then reset cur = 1
3. After the scan, the last interval might be the longest, so perform best = max(best, cur).
4. Output best.

Complexity

• Time complexity: \(O(N)\) (we examine each adjacent difference exactly once)
• Space complexity: \(O(N)\) (to store the input array \(A\); additional working space is \(O(1)\))

Implementation Notes

• When \(N=1\), the answer is 1, which is naturally handled by starting with best=1, cur=1.

• Don’t forget to compare the last interval with best, not only when encountering a break point (an update after the loop is necessary).

• Since the input can be large, in Python using sys.stdin.buffer.read() allows for faster input reading.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:2+N]

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

    print(best)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.