Overview

This problem asks you to find the longest interval in a sequence of consecutive points where the elevation difference between all adjacent points is at most \(K\).

Analysis

Problem Reformulation

This problem is about finding the length of the longest contiguous subsequence in a sequence where the absolute difference between adjacent elements is at most \(K\).

Naive Approach

One could try all combinations of starting point \(i\) and ending point \(j\), checking whether each forms a stable interval. However, this method has a time complexity of \(O(N^2)\) or \(O(N^3)\), which will not pass within the time limit (TLE) given the constraint \(N \leq 2 \times 10^5\).

Key Insight

Let’s think about the “connection” between two adjacent points.

• Points \(i\) and \(i+1\) are “connectable”: \(|A_i - A_{i+1}| \leq K\)
• Points \(i\) and \(i+1\) are “not connectable”: \(|A_i - A_{i+1}| > K\)

Finding a stable interval reduces to finding the longest consecutive “connectable” section.

For example, with \(N=5\), \(K=2\), \(A = [1, 3, 5, 10, 11]\): - Point 1→2: \(|1-3|=2 \leq 2\) ✓ - Point 2→3: \(|3-5|=2 \leq 2\) ✓ - Point 3→4: \(|5-10|=5 > 2\) ✗ (breaks here) - Point 4→5: \(|10-11|=1 \leq 2\) ✓

Therefore, there are two stable intervals: points 1~3 (length 3) and points 4~5 (length 2), with the longest being 3.

Algorithm

This typical problem of “finding the longest interval satisfying a consecutive condition” can be solved with a single pass (1-pass).

1. Initialize the current interval length current_length to 1
2. Traverse the array from left to right, checking adjacent pairs of elements
3. If the condition is satisfied: increment current_length by 1 and update the maximum
4. If the condition is not satisfied: reset current_length to 1 (start of a new interval)
5. Output the final maximum value

This method finds the answer by traversing the array just once.

Complexity

• Time complexity: \(O(N)\)
  • Only a single pass through the array is needed
• Space complexity: \(O(N)\)
  • For storing the input array \(A\)
  • Only a constant number of additional variables are used

Implementation Notes

1. Handling the case \(N=1\): When there is only one point, no adjacent elements exist, so output the answer 1 and terminate before entering the loop.

2. Initial value settings: Both max_length and current_length are initialized to 1. This is because an interval consisting of at least 1 point always exists.

3. Loop range: Iterate \(i\) from \(0\) to \(N-2\), comparing \(A[i]\) and \(A[i+1]\). Be careful to avoid out-of-bounds access.

4. Calculating absolute value: Since elevation differences are treated the same whether going up or down, use abs() to take the absolute value.

   Source Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    if N == 1:
        print(1)
        return
    
    max_length = 1
    current_length = 1
    
    for i in range(N - 1):
        if abs(A[i] - A[i + 1]) <= K:
            current_length += 1
            max_length = max(max_length, current_length)
        else:
            current_length = 1
    
    print(max_length)

solve()

---

This editorial was generated by claude4.5opus.