概要

この問題は、配列の中で「連続していて、左から右へ標高が下がらない区間」の長さの最大値を求める問題です。
言い換えると、最長の連続する広義単調増加部分列（連続区間）の長さを求めればよいです。

考察

「登り坂」は、区間 \([l, r]\) に対してすべての \(i\) について \(A_i \leq A_{i+1}\) が成り立つ区間です。
つまり、隣り合う地点を見て、標高が下がっていない間は登り坂が続くと考えられます。

重要な気づき

ある地点 \(i\) まで見たとき、

• もし \(A_{i-1} \leq A_i\) なら、前の登り坂をそのまま延長できる
• もし \(A_{i-1} > A_i\) なら、そこで登り坂は途切れるので長さは \(1\) に戻る

という性質があります。

たとえば

\(A = [2, 2, 5, 3, 4, 4, 1]\)

のとき、各位置で「その位置を右端とする登り坂の長さ」を考えると、

• \(2\) → 長さ \(1\)
• \(2\) → 前以下でないので長さ \(2\)
• \(5\) → 前以下でないので長さ \(3\)
• \(3\) → 下がったので長さ \(1\)
• \(4\) → 長さ \(2\)
• \(4\) → 長さ \(3\)
• \(1\) → 下がったので長さ \(1\)

となり、最大は \(3\) です。

素朴な方法がなぜだめか

すべての区間 \([l, r]\) を試して、その区間が登り坂かを判定する方法を考えると、

• 区間の数が \(O(N^2)\)$
• 各区間の判定に最大 \(O(N)\)$

かかるので、最悪 \(O(N^3)\)$ になります。

少し工夫して各区間の判定を速くしても、全区間を試すだけで \(O(N^2)\)\( かかります。 \)N \leq 10^5$ なので、これは間に合いません。

どう解決するか

登り坂が続いているかどうかは、隣接する2点の比較だけで決まります。
したがって、左から右へ1回見るだけで、

• 今続いている登り坂の長さ cur
• これまでの最大長 ans

を更新していけば十分です。

アルゴリズム

1. ans = 1, cur = 1 で初期化する

   • 地点が1個だけの区間も登り坂なので、最初は長さ \(1\)

2. \(i = 1\) から \(N-1\) まで順に見る

3. もし \(A_{i-1} \leq A_i\) なら

   • 今の登り坂を延長できるので cur += 1

4. そうでなければ

   • 登り坂が途切れるので cur = 1

5. 毎回 ans = max(ans, cur) とする

6. 最後に ans を出力する

具体例

\(A = [1, 3, 3, 2, 4]\) を考えます。

• 最初：cur = 1, ans = 1
• \(1 \leq 3\) なので cur = 2, ans = 2
• \(3 \leq 3\) なので cur = 3, ans = 3
• \(3 > 2\) なので cur = 1, ans = 3
• \(2 \leq 4\) なので cur = 2, ans = 3

答えは \(3\) です。
実際、区間 \([1, 3] = [1, 3, 3]\) が最長の登り坂になっています。

計算量

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

実装のポイント

• 等しい場合も登り坂に含まれるので、条件は < ではなく <= です。

• 長さ \(1\) の区間も必ず登り坂なので、ans と cur は最初に \(1\) で初期化します。

• 配列を左から1回なめるだけで答えが求まります。

  ソースコード

import sys

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

    ans = 1
    cur = 1

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

    print(ans)

if __name__ == "__main__":
    main()

---

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