[백준] 2491번 수열 파이썬 풀이

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

2491번: 수열

---

1. 접근 풀이

• 연속해서 커지는/작아지는 수열 개수를 저장할 increase / decrease 리스트 2개가 필요하다.

각 리스트에 연속해서 커지고 / 작아지고 있는 수열의 개수를 누적해서 저장한다.

 

예를 들어 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내는 과정은 이러하다. 입력 받은 수열의 첫 번째 숫자인 4는 일단 1개로 카운트한다. 두 번째 숫자 1은 4보다 작으므로, 연속해서 작아지는 수열의 길이는 현재 2가 됐다. 그러나 세 번째 숫자 3은 이전 숫자인 1보다 크므로, 더 이상 연속해서 작아지고 있지 않다. 따라서 세 번째 숫자부터는 새로운 수열이 시작됐다고 간주하고 1로 초기화한다. 이 과정을 끝까지 반복한 이후에 decrease 내 가장 큰 숫자를 뽑아내면 그것이 바로 가장 긴 연속해서 작아지는 (같은 것 포함) 수열 중 가장 긴 수열의 길이이다.

최종 정답은 increase의 가장 긴 수열의 길이와 decrease의 가장 긴 수열의 길이를 서로 비교하여 둘 중 더 큰 값이 된다.

 

 

 

2. 정답 코드

n = int(input())
data = list(map(int, input().split()))

increase = [0] * n
decrease = [0] * n
increase[0] = 1
decrease[0] = 1

for i in range(1, n):
    increase[i] = increase[i - 1] + 1 if data[i - 1] <= data[i] else 1
    decrease[i] = decrease[i - 1] + 1 if data[i - 1] >= data[i] else 1

print(max(max(increase), max(decrease)))