Overview

Given \(N\) days of temperature data, find the maximum number of consecutive days where the temperature is strictly increasing.

Analysis

Understanding the Problem

A “rising period” is a period where the temperature on each consecutive day is always higher than the previous day.

For example, if the temperatures are [10, 12, 15, 13, 14, 16, 18]: - Days 1-3: \(10 < 12 < 15\) → 3-day rising period - Days 4-7: \(13 < 14 < 16 < 18\) → 4-day rising period

In this case, the longest is 4 days.

Problems with the Naive Approach

A method that examines all contiguous subsequences by trying all combinations of start position \(l\) and end position \(r\) would have \(O(N^2)\) time complexity. When \(N\) is at most \(2 \times 10^5\), this will not be fast enough.

Key Insight for an Efficient Solution

An important observation is that a rising period ends when the temperature drops (or stays the same).

In other words, while scanning the array once: - If the temperature rises, extend the current rising period by 1 day - If the temperature does not rise, reset the current rising period

By managing it this way, we can solve the problem in \(O(N)\).

Algorithm

1. Initialize both max_length (longest rising period) and current_length (currently tracked rising period) to 1
2. Iterate through \(i = 1\) to \(N-1\):
   • If \(A[i] > A[i-1]\) (temperature rises):
     • Increment current_length by 1
     • Update max_length by comparing with current_length
   • Otherwise (temperature does not rise):
     • Reset current_length to 1 (start of a new rising period)
3. Output max_length

Walkthrough with a Concrete Example

Input: N=7, A=[10, 12, 15, 13, 14, 16, 18]

\(i\)	\(A[i-1]\)	\(A[i]\)	Comparison Result	current_length	max_length
1	10	12	Rising	2	2
2	12	15	Rising	3	3
3	15	13	Falling	1	3
4	13	14	Rising	2	3
5	14	16	Rising	3	3
6	16	18	Rising	4	4

Answer: 4

Complexity

• Time complexity: \(O(N)\) (only one pass through the array)
• Space complexity: \(O(N)\) (required to store the input array)

Implementation Notes

• Handling the case when \(N = 1\): When there is only 1 day, there is nothing to compare against, but the answer is 1 as a 1-day rising period. Although this is handled specially in the code, the main logic also initializes max_length = 1, so when \(N = 1\), the loop does not execute and 1 is correctly output.

• Be careful with equality: The condition is A[i] > A[i-1] (strict increase). If you use A[i] >= A[i-1] instead, consecutive days with the same temperature would be included in the rising period, leading to an incorrect answer.

  Source Code

N = int(input())
A = list(map(int, input().split()))

if N == 1:
    print(1)
else:
    max_length = 1
    current_length = 1
    
    for i in range(1, N):
        if A[i] > A[i-1]:
            current_length += 1
            max_length = max(max_length, current_length)
        else:
            current_length = 1
    
    print(max_length)

---

This editorial was generated by claude4.5opus.