概要

配列 \(A\) の中で、連続する区間がずっと \(A_i \leq A_{i+1}\) を満たすような「最長の非減少連続部分列（連続区間）」の長さを求める問題です。
左から1回見るだけで、現在の登り坂の長さを更新していけば解けます。

考察

まず「登り坂」は連続区間であることが重要です。
つまり、ある地点で条件 \(A_i \leq A_{i+1}\) が壊れたら、その先は新しい登り坂を作り直すしかありません。

重要な気づき

• 今見ている地点 \(a\) と1つ前の地点 prev を比較すれば、
  
  • prev <= a なら今の登り坂を延長できる
  • そうでなければ登り坂は途切れるので長さを1にリセット
• 各時点で「今の登り坂の長さ cur_len」と「これまでの最大 ans」を持てば十分です。

素朴解が厳しい理由

例えば各始点 \(l\) から右へ伸ばして最長を調べる、という方法だと最悪で
\(1 + 2 + \cdots + N = O(N^2)\)
になります。\(N \le 10^5\) なので間に合いません。

解決策

配列を左から1回だけ走査して、隣接2要素の比較結果で cur_len を更新します。
これなら各要素を1回ずつ処理するだけなので高速です。

アルゴリズム

1. \(N\) を読む。
2. 最初の標高を prev として読む。
3. cur_len = 1, ans = 1 で初期化。
4. 残り \(N-1\) 個の標高 a について順に:
   • もし prev <= a なら cur_len += 1
   • そうでなければ cur_len = 1
   • ans = max(ans, cur_len)
   • prev = a に更新
5. ans を出力。

具体例

\(A = [2, 2, 5, 3, 4, 4]\) のとき - \(2 \to 2\) : 伸びる (cur=2) - \(2 \to 5\) : 伸びる (cur=3) - \(5 \to 3\) : 途切れる (cur=1) - \(3 \to 4\) : 伸びる (cur=2) - \(4 \to 4\) : 伸びる (cur=3)

最大は 3 です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 入力が多いので sys.stdin.readline を使うと安全です。

• N=1 のときも、初期値 cur_len=ans=1 で正しく処理できます。

• 条件は「広義単調増加」なので比較は < ではなく <= です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    
    prev = int(input().strip())
    cur_len = 1
    ans = 1
    
    for _ in range(1, N):
        a = int(input().strip())
        if prev <= a:
            cur_len += 1
        else:
            cur_len = 1
        if cur_len > ans:
            ans = cur_len
        prev = a
    
    print(ans)

if __name__ == "__main__":
    main()

---

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