Overview

Given temperature data over \(N\) days, the problem asks to find the longest consecutive number of days that are extreme heat days (temperature \(K\) degrees or above).

Analysis

This problem requires finding the maximum length of consecutive intervals of extreme heat days. We examine each day in order, incrementing a counter as long as extreme heat days continue, and resetting the counter when a non-extreme heat day appears. By progressively updating the length of consecutive extreme heat days in this manner, we can solve the problem efficiently. A naive approach of examining all consecutive intervals is conceivable, but since \(N\) can be as large as \(10^6\), an \(O(N^2)\) method would be too slow. Therefore, we use a linear-time algorithm that solves the problem in a single pass.

Algorithm

1. Initialize a variable current to 0, which holds the current number of consecutive extreme heat days.
2. Initialize a variable max_streak to 0, which holds the longest consecutive extreme heat day count found so far.
3. Examine each day’s temperature in order:
   • If the temperature is \(K\) or above, increment current by 1.
   • Otherwise, if current is greater than max_streak, update max_streak, then reset current to 0.
4. After the loop, compare current with max_streak and update accordingly, in case the last interval ends with extreme heat days.
5. Output max_streak.

This algorithm is efficient because it scans the array only once.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (for storing the input data)

Implementation Notes

• For reading input, use sys.stdin.read().split() to read everything at once and store it in a list. This allows fast processing even with large amounts of input.

• Be careful not to forget handling the case where the last interval ends with extreme heat days. After the loop, you need to compare current with max_streak and update accordingly.

• If there are no extreme heat days at all, max_streak remains at its initial value of 0, so 0 is correctly output.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    max_streak = 0
    current = 0
    
    for temp in A:
        if temp >= K:
            current += 1
        else:
            if current > max_streak:
                max_streak = current
            current = 0
            
    if current > max_streak:
        max_streak = current
        
    print(max_streak)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.