概要

\(N\) 日間の気温データから、気温が厳密に増加し続ける連続した期間の最大日数を求める問題です。

考察

問題の理解

「上昇期間」とは、連続する日の気温が常に前日より高くなっている期間のことです。

例えば、気温が [10, 12, 15, 13, 14, 16, 18] の場合： - 1〜3日目: \(10 < 12 < 15\) → 3日間の上昇期間 - 4〜7日目: \(13 < 14 < 16 < 18\) → 4日間の上昇期間

この場合、最長は 4日間 となります。

素朴なアプローチの問題点

すべての連続部分列を調べる方法では、開始位置 \(l\) と終了位置 \(r\) のすべての組み合わせを試すと \(O(N^2)\) の計算量がかかります。\(N\) が最大 \(2 \times 10^5\) の場合、これは間に合いません。

効率的な解法への気づき

重要な観察として、上昇期間は「気温が下がった（または同じになった）時点」で途切れる ということがあります。

つまり、配列を1回走査しながら： - 気温が上昇したら、現在の上昇期間を1日延長 - 気温が上昇しなかったら、現在の上昇期間をリセット

このように管理すれば、\(O(N)\) で解けます。

アルゴリズム

1. max_length（最長の上昇期間）と current_length（現在追跡中の上昇期間）を両方 1 で初期化
2. \(i = 1\) から \(N-1\) まで順に見ていく：
   • もし \(A[i] > A[i-1]\) なら（気温が上昇）：
     • current_length を 1 増やす
     • max_length を current_length と比較して更新
   • そうでなければ（気温が上昇していない）：
     • current_length を 1 にリセット（新しい上昇期間の開始）
3. max_length を出力

具体例での動作確認

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

\(i\)	\(A[i-1]\)	\(A[i]\)	比較結果	current_length	max_length
1	10	12	上昇	2	2
2	12	15	上昇	3	3
3	15	13	下降	1	3
4	13	14	上昇	2	3
5	14	16	上昇	3	3
6	16	18	上昇	4	4

答え: 4

計算量

• 時間計算量: \(O(N)\)（配列を1回走査するだけ）
• 空間計算量: \(O(N)\)（入力配列の格納に必要）

実装のポイント

• \(N = 1\) の場合の処理: 1日だけの場合、比較する相手がいませんが、1日だけの上昇期間として答えは 1 です。コード中では特別に処理していますが、実はメインのロジックでも max_length = 1 で初期化しているため、N = 1 の場合もループが実行されず正しく 1 が出力されます。

• 等号に注意: 条件は A[i] > A[i-1]（厳密な増加）です。A[i] >= A[i-1] としてしまうと、同じ気温が続く場合も上昇期間に含めてしまい、誤答になります。

  ソースコード

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)

---

この解説は claude4.5opus によって生成されました。