Overview

This problem asks us to find the maximum length of a contiguous subarray where all elements are within a specified range \([L, R]\).

Analysis

Key Insight

The key point of this problem is the “contiguous” condition. Since all trees in the interval must satisfy the sweetness condition, if even one tree fails to meet the condition, the interval is broken at that point.

Naive Approach and Its Issues

A naive approach would be to enumerate all intervals \([l, r]\) and check whether all elements in each interval satisfy the condition.

• Number of interval candidates: \(O(N^2)\)
• Checking each interval: \(O(N)\)
• Total: \(O(N^3)\)

For \(N = 2 \times 10^5\), this is far too slow.

Solution

We can scan the array from left to right once while tracking the length of the current contiguous interval that satisfies the condition.

Let’s consider a concrete example: - \(L = 5, R = 10\) - \(T = [6, 8, 7, 3, 9, 10, 8]\)

\(i\)	\(T_i\)	Satisfies condition?	current_length	max_length
0	6	○	1	1
1	8	○	2	2
2	7	○	3	3
3	3	×	0	3
4	9	○	1	3
5	10	○	2	3
6	8	○	3	3

The answer is \(3\).

Algorithm

1. Initialize current_length (length of the current contiguous interval) and max_length (maximum length) to \(0\)
2. Scan the array from left to right
3. For each element \(T_i\):
   • If \(L \leq T_i \leq R\), increment current_length by \(1\) and update max_length
   • Otherwise, reset current_length to \(0\) (the interval is broken)
4. Output the final max_length

This algorithm is also called a “run-length style approach” and is a typical technique for collectively processing consecutive elements that share the same property.

Complexity

• Time complexity: \(O(N)\)
  • We only scan the array once
• Space complexity: \(O(N)\)
  • Required for storing the input array \(T\) (additional variables used are \(O(1)\))

Implementation Notes

• Don’t forget to reset current_length to \(0\) when encountering an element that doesn’t satisfy the condition

• Updating max_length only needs to be done when finding an element that satisfies the condition

• In Python, you can write a concise range check using L <= T[i] <= R

  Source Code

def solve():
    N, L, R = map(int, input().split())
    T = list(map(int, input().split()))
    
    max_length = 0
    current_length = 0
    
    for i in range(N):
        if L <= T[i] <= R:
            current_length += 1
            max_length = max(max_length, current_length)
        else:
            current_length = 0
    
    print(max_length)

solve()

---

This editorial was generated by claude4.5opus.