概要

数列の中で、値が非減少（広義単調増加）である連続部分列の最大長を求める問題です。

考察

重要な気づき

「登り坂」とは、隣り合う地点の標高を比較したとき、すべて \(A_i \leq A_{i+1}\) が成り立つ連続区間のことです。つまり、途中で標高が下がった瞬間に「登り坂」は途切れます。

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

すべての区間 \((l, r)\) の組を試し、それぞれが登り坂かどうかを判定する方法が考えられます。区間の組は \(O(N^2)\) 通りあり、各区間の判定に最大 \(O(N)\) かかるため、全体で \(O(N^3)\) となり、\(N = 10^5\) では到底間に合いません。

どう解決するか

実は、配列を左から順に1回走査するだけで答えが求められます。ポイントは次の通りです：

• 現在の「登り坂」の長さを変数 cur_len で管理する
• \(A_i \geq A_{i-1}\) なら登り坂が続いているので cur_len を \(1\) 増やす
• \(A_i < A_{i-1}\) なら登り坂が途切れたので cur_len を \(1\) にリセットする
• 各ステップで、これまでの最大値 max_len を更新する

具体例

例えば \(A = [3, 5, 5, 2, 4, 7, 1]\) の場合：

\(i\)	\(A_i\)	比較	cur_len	max_len
0	3	—	1	1
1	5	\(5 \geq 3\) ✓	2	2
2	5	\(5 \geq 5\) ✓	3	3
3	2	\(2 < 5\) ✗	1	3
4	4	\(4 \geq 2\) ✓	2	3
5	7	\(7 \geq 4\) ✓	3	3
6	1	\(1 < 7\) ✗	1	3

答えは \(3\) です（区間 \([3, 5, 5]\) または \([2, 4, 7]\)）。

アルゴリズム

1. max_len = 1、cur_len = 1 で初期化する（地点が1個でも登り坂なので最小値は1）。
2. \(i = 1\) から \(N-1\) まで順に走査する：
   • \(A_i \geq A_{i-1}\) なら cur_len を \(1\) 増やす。
   • そうでなければ cur_len を \(1\) にリセットする。
   • cur_len > max_len なら max_len を更新する。
3. max_len を出力する。

この手法は「ランレングス的な走査」とも呼ばれ、条件を満たす連続区間の最大長を求める定番のテクニックです。

計算量

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

実装のポイント

• cur_len と max_len の初期値はどちらも \(1\) にします。\(N = 1\) のとき（地点が1個だけのとき）もループに入らず正しく \(1\) を出力できます。

• 条件は \(A_i > A_{i-1}\)（狭義単調増加）ではなく \(A_i \geq A_{i-1}\)（広義単調増加）であることに注意してください。問題文の「非減少」という条件を正確に反映する必要があります。

  ソースコード

N = int(input())
A = [int(input()) for _ in range(N)]

max_len = 1
cur_len = 1

for i in range(1, N):
    if A[i] >= A[i-1]:
        cur_len += 1
    else:
        cur_len = 1
    if cur_len > max_len:
        max_len = cur_len

print(max_len)

---

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