Overview

Given temperature data over \(N\) days, this problem asks us to find the maximum length of a consecutive interval where the highest temperature is \(K\) or above (extremely hot days). This is a classic problem of finding the “longest run of consecutive elements satisfying a condition.”

Analysis

Essence of the Problem

We want to find the maximum length of a consecutive interval in an array where elements satisfy a certain condition (\(A_i \geq K\)).

Thinking Through a Concrete Example

For example, suppose \(N = 10\), \(K = 35\), and the temperatures are given as follows:

33 36 37 35 34 38 39 40 36 33

Representing whether each day is an extremely hot day with ○/×:

×  ○  ○  ○  ×  ○  ○  ○  ○  ×

There are two consecutive intervals of extremely hot days: “○○○” (length 3) and “○○○○” (length 4), so the maximum is 4.

Naive Approach

One could enumerate all intervals \((l, r)\) and check whether every day in each interval is an extremely hot day. However, there are \(O(N^2)\) intervals, and checking each one takes \(O(N)\), resulting in \(O(N^3)\) overall. This is far too slow for the constraint \(N \leq 10^6\).

Efficient Solution: Run-Length Style Scanning

It suffices to scan the array from the beginning once while maintaining a counter for “how many consecutive extremely hot days we currently have.”

• If the current day is an extremely hot day, increment the counter by \(+1\).
• If it is not an extremely hot day, reset the counter to \(0\).
• If the counter value exceeds the previous maximum, record it.

With this method, the answer can be obtained by scanning the array just once.

Algorithm

1. Initialize max_streak = 0 (maximum consecutive days) and current_streak = 0 (current consecutive days).
2. For \(i = 1, 2, \ldots, N\) in order, do the following:
   • If \(A_i \geq K\), increment current_streak by \(1\) and update max_streak with max(max_streak, current_streak).
   • If \(A_i < K\), reset current_streak to \(0\).
3. Output the final max_streak.

If there are no extremely hot days at all, current_streak is never incremented, so max_streak remains at its initial value of \(0\) and is output as-is.

Complexity

• Time complexity: \(O(N)\) — just a single scan through the array
• Space complexity: \(O(N)\) — an array is used for reading input (the additional memory needed for the scan itself is \(O(1)\))

Implementation Notes

• Fast input: Since \(N\) can be as large as \(10^6\), in Python we use sys.stdin.buffer.read() to read all input at once and split it into tokens with split() to speed up input. This is significantly faster than calling input() \(N\) times.

• Avoiding the max function: Instead of calling the max() function every iteration inside the loop, we update using the comparison if current_streak > max_streak. In Python, this avoids function call overhead, which can make a difference over \(10^6\) iterations.

• Watch out for index offsets: In the input data, input_data[0] is \(N\), input_data[1] is \(K\), and input_data[2] onward are \(A_1, A_2, \ldots, A_N\), so accessing \(A_i\) requires input_data[i + 2].

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    
    max_streak = 0
    current_streak = 0
    
    for i in range(N):
        if int(input_data[i + 2]) >= K:
            current_streak += 1
            if current_streak > max_streak:
                max_streak = current_streak
        else:
            current_streak = 0
    
    print(max_streak)

main()

---

This editorial was generated by claude4.6opus-thinking.