[백준] 11054 가장 긴 바이토닉 부분 수열 in python

https://www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

 

이문제는 가장 긴 증가하는 수열 + 가장 긴 감소하는 수열을 합쳐놓은 문제같다 ㅋㅋ

마침 두개 다 풀었고, 그래서 나는 

1. 가장 긴 증가하는 수열 만들기 : dp

2. 가장 긴 감소하는 수열 만들기 : dp2

3. 합친 수열중에서 가장 길이가 긴 수열 값 구하기 -> dp3 테이블을 만들었다. 

 

# 11054 가장 긴 바이토닉 수열

n = int(input())
array = list(map(int, input().split()))
dp = [1]*n
dp2 = [1]*n
dp3 = [0]*n
# 증가하는 수열
for i in range(n):
    for j in range(i):
        if array[i] > array[j]:
            dp[i] = max(dp[i], dp[j] +1)

max_index = 0
max_length = 0

for i in range(n):
    if dp[i] > max_length:
        max_length = dp[i]
        max_index = i

# 감소하는 수열
for i in range(n-1, -1, -1):
    for j in range(i+1, n):
        if array[i] > array[j]:
            dp2[i] = max(dp2[i], dp2[j]+1)

for i in range(n):
    dp3[i] = dp[i] + dp2[i] -1
print(max(dp3))

ㅋㅋㅋㅋ 나의 시도들...