概要

\(N\) 日間の気温データから、気温が厳密に（より大きく）上がり続けている連続した期間の最大日数を求める問題です。

考察

この問題のポイントは、「上昇が途切れたら、そこまでの長さを記録して新しく数え直せばよい」という点にあります。

素朴なアプローチ

すべての「開始日」と「終了日」の組み合わせ（\(O(N^2)\) 通り）を調べると、最大で \(N=2 \times 10^5\) なので、計算回数が約 \(4 \times 10^{10}\) 回となり、制限時間内に終わりません。

効率的なアプローチ

気温の配列を左から右へ 1 回だけ見ていくことを考えます。 - \(i\) 日目の気温が \(i-1\) 日目よりも高い場合：上昇期間が継続しているので、現在のカウントを 1 増やします。 - \(i\) 日目の気温が \(i-1\) 日目以下の場合：上昇期間が途切れたことになります。これまでのカウントの最大値を記録し、カウントを 1（その日単独の長さ）にリセットします。

このように、一度の走査で答えを求めることができます。

アルゴリズム

以下の手順で解くことができます。

1. 最大の長さを保持する変数 max_len と、現在の上昇期間の長さを保持する変数 current_len をそれぞれ \(1\) で初期化します。
2. \(2\) 日目から \(N\) 日目まで、順番に以下の処理を行います：
   • もし「今日の気温 > 前日の気温」であれば、current_len を \(1\) 増やす。
   • そうでなければ、max_len を max(max_len, current_len) で更新し、current_len を \(1\) に戻す。
3. 全ての日程を確認した後、最後の上昇期間が最大である可能性を考慮し、もう一度 max_len を max(max_len, current_len) で更新します。
4. max_len を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 配列を 1 回だけ走査するため、要素数 \(N\) に比例した時間で終わります。
• 空間計算量: \(O(N)\)
  • 入力された気温データをリストに格納するために \(O(N)\) のメモリを使用します。

実装のポイント

• 「より大きい」の判定: 問題文に \(A_l < A_{l+1} < \cdots\) とあるため、同じ気温（\(A_i = A_{i-1}\)）の場合は上昇期間が途切れる点に注意してください。

• ループ終了後の更新: 最終日まで気温が上がり続けた場合、ループ内の else 処理（リセット時の更新）が実行されません。そのため、ループの外で最後にもう一度 max_len を更新する必要があります。

• 入力の高速化: \(N\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと高速に動作します。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Nの取得
    n = int(input_data[0])
    # 気温データの取得
    if n == 0:
        print(0)
        return
    
    a = list(map(int, input_data[1:]))
    
    max_len = 1
    current_len = 1
    
    # 配列を走査して連続上昇期間を計算
    for i in range(1, n):
        if a[i] > a[i-1]:
            current_len += 1
        else:
            if current_len > max_len:
                max_len = current_len
            current_len = 1
            
    # 最後の要素まで上昇が続いていた場合の更新
    if current_len > max_len:
        max_len = current_len
        
    print(max_len)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。