Overview

This problem asks us to find the maximum length of a “contiguous interval where the elevation does not decrease from left to right” within an array. In other words, we need to find the length of the longest contiguous non-decreasing subsequence (contiguous interval).

Analysis

An “uphill slope” is an interval \([l, r]\) where \(A_i \leq A_{i+1}\) holds for all \(i\) within it. In other words, by looking at adjacent points, the uphill slope continues as long as the elevation does not decrease.

Key Observation

When we have examined up to point \(i\):

• If \(A_{i-1} \leq A_i\), we can extend the previous uphill slope as is
• If \(A_{i-1} > A_i\), the uphill slope is broken there, so the length resets to \(1\)

For example, given

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

if we consider “the length of the uphill slope ending at each position”:

• \(2\) → length \(1\)
• \(2\) → not less than previous, so length \(2\)
• \(5\) → not less than previous, so length \(3\)
• \(3\) → decreased, so length \(1\)
• \(4\) → length \(2\)
• \(4\) → length \(3\)
• \(1\) → decreased, so length \(1\)

The maximum is \(3\).

Why the Naive Approach Fails

If we consider trying all intervals \([l, r]\) and checking whether each interval is an uphill slope:

• The number of intervals is \(O(N^2)\)
• Checking each interval takes up to \(O(N)\)

So in the worst case it takes \(O(N^3)\).

Even with some optimization to speed up the check for each interval, just trying all intervals costs \(O(N^2)\). Since \(N \leq 10^5\), this is too slow.

How to Solve It

Whether an uphill slope continues is determined by comparing only two adjacent points. Therefore, by scanning from left to right just once and maintaining:

• The current uphill slope length cur
• The maximum length so far ans

and updating them, we can solve the problem.

Algorithm

1. Initialize ans = 1, cur = 1

   • An interval of just one point is also an uphill slope, so the initial length is \(1\)

2. Iterate \(i\) from \(1\) to \(N-1\)

3. If \(A_{i-1} \leq A_i\):

   • The current uphill slope can be extended, so cur += 1

4. Otherwise:

   • The uphill slope is broken, so cur = 1

5. Each time, update ans = max(ans, cur)

6. Output ans at the end

Concrete Example

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

• Initially: cur = 1, ans = 1
• \(1 \leq 3\), so cur = 2, ans = 2
• \(3 \leq 3\), so cur = 3, ans = 3
• \(3 > 2\), so cur = 1, ans = 3
• \(2 \leq 4\), so cur = 2, ans = 3

The answer is \(3\). Indeed, the interval \([1, 3] = [1, 3, 3]\) is the longest uphill slope.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

• Equal values are also included in uphill slopes, so the condition is <=, not <.

• An interval of length \(1\) is always an uphill slope, so ans and cur are initialized to \(1\).

• The answer can be obtained by scanning the array from left to right just once.

  Source Code

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()

---

This editorial was generated by gpt-5.4-high.