본문 바로가기

코딩테스트 준비

LIS, DP - 백준 - 가장 긴 바이토닉 부분 수열

N = int(input())
lst = list(map(int, input().strip().split()))
dp = [0 for i in range(N)]
dp2 = [0 for i in range(N)]
# 정방향으로 LIS를 찾는다.
for i in range(N):
for j in range(i):
if (lst[i] > lst[j] and dp[i] < dp[j]):
dp[i] = dp[j]
dp[i] += 1
# 역방향으로 LIS를 찾는다.
for i in range(N - 1, -1, -1):
for j in range(N - 1, i, -1):
if (lst[i] > lst[j] and dp2[i] < dp2[j]):
dp2[i] = dp2[j]
dp2[i] += 1
print(dp)
print(dp2)
MAX = 0
for i in range(N):
if dp[i] + dp2[i] > MAX:
MAX = dp[i] + dp2[i]
print(MAX - 1)