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

문제

 

풀이.

저번에 포스트 했던 LIS를 구하는 알고리즘을 응용한 문제이다.

앞에서 부터 구한 LIS와 뒤에서 부터 구한 LIS를 더해서 최댓값을 출력하면 된다.

단 두개를 더하고 숫자 하나는 겹치기 때문에 -1을 해줘야한다.

 

 

소스코드.

import sys

A = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split()))
dp1 = [0] * A
dp2 = [0] * A
result = [0] * A
for i in range(A):
    for j in range(i):
        if seq[i] > seq[j] and dp1[i] < dp1[j]:
            dp1[i] = dp1[j]
    dp1[i] += 1
    result[i] += dp1[i]

for i in range(A-1, -1, -1):
    for j in range(A-1, i, -1):
        if seq[i] > seq[j] and dp2[i] < dp2[j]:
            dp2[i] = dp2[j]
    dp2[i] += 1
    result[i] += dp2[i]


print(max(result) - 1)