Overview

This problem asks you to find the maximum length of a contiguous subsequence in a sequence where the values are non-decreasing (monotonically non-decreasing).

Analysis

Key Insight

An “uphill slope” is a contiguous interval where, when comparing the elevations of adjacent points, \(A_i \leq A_{i+1}\) holds for all consecutive pairs. In other words, the “uphill slope” breaks the moment the elevation decreases.

Naive Approach and Its Issues

One could consider trying all pairs of intervals \((l, r)\) and checking whether each one is an uphill slope. There are \(O(N^2)\) pairs of intervals, and checking each interval takes up to \(O(N)\), resulting in an overall complexity of \(O(N^3)\), which is far too slow for \(N = 10^5\).

How to Solve It

In fact, the answer can be found by scanning the array from left to right just once. The key points are:

• Maintain the length of the current “uphill slope” in a variable cur_len
• If \(A_i \geq A_{i-1}\), the uphill slope continues, so increment cur_len by \(1\)
• If \(A_i < A_{i-1}\), the uphill slope is broken, so reset cur_len to \(1\)
• At each step, update the running maximum max_len

Concrete Example

For example, given \(A = [3, 5, 5, 2, 4, 7, 1]\):

\(i\)	\(A_i\)	Comparison	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

The answer is \(3\) (the interval \([3, 5, 5]\) or \([2, 4, 7]\)).

Algorithm

1. Initialize max_len = 1 and cur_len = 1 (even a single point counts as an uphill slope, so the minimum value is 1).
2. Scan from \(i = 1\) to \(N-1\) in order:
   • If \(A_i \geq A_{i-1}\), increment cur_len by \(1\).
   • Otherwise, reset cur_len to \(1\).
   • If cur_len > max_len, update max_len.
3. Output max_len.

This technique is sometimes called a “run-length style scan” and is a classic method for finding the maximum length of a contiguous interval satisfying a given condition.

Complexity

• Time complexity: \(O(N)\) (only a single scan through the array)
• Space complexity: \(O(N)\) (needed to store the array \(A\); the variables used for scanning are \(O(1)\))

Implementation Notes

• The initial values of both cur_len and max_len should be \(1\). When \(N = 1\) (only one point), the loop is never entered and the correct answer of \(1\) is output.

• Note that the condition is \(A_i \geq A_{i-1}\) (non-strictly monotonically increasing), not \(A_i > A_{i-1}\) (strictly monotonically increasing). It is important to accurately reflect the “non-decreasing” condition stated in the problem.

  Source Code

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)

---

This editorial was generated by claude4.6opus-thinking.