[백준 BOJ_11054] 가장 긴 바이토닉 부분 수열 Python 풀이

출처: 백준 온라인 저지

문제

풀이

코드

N = int(input())
A = list(map(int, input().split()))
cache = [[0 for _ in range(2)] for _ in range(N)]
bitonic = [1 for _ in range(N)]
for i in range(N):
    for lo in range(i):
        if A[i] > A[lo] and cache[i][0] <= cache[lo][0]:
            cache[i][0] = cache[lo][0] + 1
    bitonic[i] += cache[i][0]
for j in range(N-1, -1, -1):
    for hi in range(N-1, j, -1):
        if A[j] > A[hi] and cache[j][1] <= cache[hi][1]:
            cache[j][1] = cache[hi][1] + 1
    bitonic[j] += cache[j][1]
print(max(bitonic))