概要

与えられた気温列 \(A_1,\dots,A_N\) について、連続する部分列の中で「厳密に増加」している最長の長さを求めます。

考察

「上昇期間」は連続区間であり、条件は \(A_{i-1} < A_i\) が区間内でずっと成り立つことです。
つまり、隣り合う2日を見て 増加しているかどうか だけ分かれば、上昇期間の長さを伸ばせるか・リセットすべきかが決まります。

素朴に全ての区間 \((l,r)\) を調べると、区間は \(O(N^2)\) 個あり、各区間で増加判定をするとさらに時間がかかり \(N \le 2\times 10^5\) では確実に間に合いません（TLE）。

そこで、左から1回走査しながら、 - 直前より増加しているなら現在の連続増加長 cur を \(+1\) - そうでなければ cur=1 に戻す
という更新をすることで、最長値 best を同時に求められます。

例：\([3, 5, 4, 6, 7]\) - \(3 \to 5\) は増加：cur=2 - \(5 \to 4\) は増加でない：cur=1 - \(4 \to 6\) は増加：cur=2 - \(6 \to 7\) は増加：cur=3
よって答えは \(3\)（\(4,6,7\)）。

アルゴリズム

1. best=1, cur=1 で初期化する（\(N=1\) でも答えは 1）。
2. \(i=2\) 日目から \(N\) 日目まで順に見る（配列では i=1..N-1）。
3. もし \(A_i > A_{i-1}\) なら、連続増加が続くので cur += 1。
4. そうでなければ増加が途切れるので cur = 1。
5. 各ステップで best = max(best, cur) を更新する。
6. best を出力する。

計算量

• 時間計算量: \(O(N)\)（1回の走査のみ）
• 空間計算量: \(O(1)\)（入力配列以外は定数個の変数）

実装のポイント

• 「厳密に増加」なので条件は \(A_i > A_{i-1}\)（\(A_i \ge A_{i-1}\) ではない）に注意します。

• \(N=1\) のときも正しく答えが \(1\) になるよう、best=cur=1 から開始します。

• 入力が大きいので、Pythonでは sys.stdin.buffer.read() を使うと高速に読み込めます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n = data[0]
    a = data[1:1+n]

    best = cur = 1
    for i in range(1, n):
        if a[i] > a[i-1]:
            cur += 1
        else:
            cur = 1
        if cur > best:
            best = cur

    print(best)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。