백준 2491 - 수열 (파이썬)

https://www.acmicpc.net/problem/2491

풀이

어떤 수열이 주어졌을 때, 연속적으로 커지거나 같거나, 혹은 작아지거나 같은 부분 수열 중 가장 긴 길이를 구하는 문제이다.

1. 비내림차순 수열의 최대 길이 계산
2. 비오름차순 수열의 최대 길이 계산
3. 위 두 결과 중 최대값을 출력

A[: : -1] 로 뒤집어서 감소하거나 같은 부분 수열을 구할 수 있도록 바꾼다.

시간복잡도 분석

1. 비내림차순 수열의 계산 → O(N)
2. 비오름차순 수열의 계산 → O(N)
3. 즉, O(N)

코드

# 백준 2491 - 수열
# 분류 : 구현

N = int(input())
A = list(map(int, input().split()))

max_count = 1

count = 1
for i in range(1, N) :
    if A[i- 1] <= A[i] :
        count += 1
    else :
        count = 1
    
    max_count = max(max_count, count)

A = A[::-1]
count = 1
for i in range(1, N) :
    if A[i- 1] <= A[i] :
        count += 1
    else :
        count = 1
    
    max_count = max(max_count, count)

print(max_count)