This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) | |
'코딩테스트 준비' 카테고리의 다른 글
누적 합 알고리즘! - itertools의 accumulate() (0) | 2021.02.25 |
---|---|
재귀, 분할정복 - 백준 쿼드트리 (0) | 2021.02.25 |
전위 순회, 중위 순회, 후위 순회 (0) | 2021.02.24 |
재귀 + dp + 조합 공식 (0) | 2021.02.24 |
서로소 집합 알고리즘 (0) | 2021.02.24 |