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)

view raw 백준 가장 긴 바이토닉 부분 수열 - LIS, DP hosted with ❤ by GitHub