백준 11054 - 가장 긴 바이토닉 부분 수열 [파이썬]

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

11054번: 가장 긴 바이토닉 부분 수열

---

풀이 과정

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라 한다.

 

그렇다면 Sk를 기준으로 하는 바이토닉 수열의 길이는 Sk를 마지막으로 하는 증가하는 부분 수열의 길이 + Sk를 시작으로 하는 감소하는 부분 수열의 길이 - 1임을 알 수 있다.

 

따라서 주어진 수열의 모든 원소 K에 대해 K를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 + K를 시작으로 하는 가장 긴 감소하는 부분수열의 길이 - 1을 구한 뒤, 가장 긴 값이 바로 가장 긴 바이토닉 부분 수열의 길이이다.

 

https://greentea31.tistory.com/34

백준 11053 - 가장 긴 증가하는 부분 수열 [파이썬]

 

https://greentea31.tistory.com/62

백준 11722 - 가장 긴 감소하는 부분 수열 [파이썬]

 

이 문제는 위의 2문제의 풀이법을 합쳐서 해결할 수 있는 문제이고 각 문제의 풀이를 위한 점화식은 위의 두 글을 참고하면 된다.

 

---

소스 코드

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

d = [1 for _ in range(N)]
d2 = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if A[j] < A[i]:
            d[i] = max(d[i], d[j] + 1)

for i in range(N-1, -1, -1):
    for j in range(N-1, i, -1):
        if A[j] < A[i]:
            d2[i] = max(d2[i], d2[j] + 1)

d3 = [d[i] + d2[i] - 1 for i in range(N)]

print(max(d3))