[BOJ 11054] 가장 긴 바이토닉 부분 수열(Python)

문제

가장 긴 바이토닉 부분 수열

---

문제 해설

가장 긴 바이토닉 부분 수열이란 증가하고 있거나 감소하고 있는 부분 수열을 말합니다.

1. 모든 지점에서 가장 긴 증가,감소하는 수열의 길이를 구합니다.
2. 두 길이를 더해 가장 긴 것을 채택합니다.

가장 긴 증가하는 수열은 이 문제에서 구할 수 있습니다. 가장 긴 감소하는 수열은 시작 지점을 끝에서부터 시작하면 구할 수 있습니다.

간단한 예시를 보자면
list = 1 5 2 1 4 3 4 5 2 1

증가=1 2 2 1 3 3 4 5 2 1

감소=1 5 2 1 4 3 3 3 2 1

ans =2 7 4 2 7 6 7 8 4 2

이런 식으로 어느 지점에서 가장 긴 증가하는 수열 + 감소하는 수열을 구하면 그것이 가장 긴 바이토닉 부분 수열입니다. 그리고 증가와 감소에서 그 지점의 숫자가 하나 겹치기 때문에 -1을 해주면 됩니다.

---

풀이 코드

import sys

input = sys.stdin.readline
n = int(input())
increase = [1] * n
decrease = [1] * n
graph = list(map(int, input().split()))
# 모든 지점에서 가장 긴 증가하는, 감소하는 수열의 길이를 구한다.
# 두 길이를 더해 가장 긴 것을 채택한다.
for i in range(n):
    for j in range(i):
        if graph[i] > graph[j]:
            increase[i] = max(increase[i], increase[j] + 1)
        if graph[-i - 1] > graph[-j - 1]:
            decrease[-i - 1] = max(decrease[-i - 1], decrease[-j - 1] + 1)

answer = [increase[i] + decrease[i] for i in range(n)]
print(max(answer) - 1)

---