[DP] Python - 11054번 가장 긴 바이토닉 부분 수열

N = int(input())
A = list(map(int, input().split()))

dpAscend = [0]*N
for i in range(N):
    for j in range(i):
        if A[i]>A[j] and dpAscend[i]<=dpAscend[j]:
            dpAscend[i] = dpAscend[j]+1

dpDescend = [0]*N
for i in range(N-1, -1, -1):
    for j in range(N-1, i, -1):
        if A[i]>A[j] and dpDescend[i]<=dpDescend[j]:
            dpDescend[i] = dpDescend[j]+1

RET = 0
for i in range(N):
    RET = max(RET, dpAscend[i]+dpDescend[i]+1)
print(RET)

매우 직관적인 그림을 그려봤습니다.

 

각각의 dp는 '가장 긴 증가하는 부분 수열의 길이'를 나타내고 있습니다.

③에서 dpAscend+dpDescend가 의미하는 바는, '해당 인덱스에서 가장 긴 바이토닉 부분 수열'입니다.

그것들을 for문으로 돌면서 max값(RET)을 찾으면 문제가 해결됩니다.

 

제 코드를 기반으로, 해당 문제의 예시 케이스를 실행했을 때의 두 dp의 값은 다음과 같습니다.

 

[INPUT]

10

1 5 2 1 4 3 4 5 2 1

 

[OUTPUT]

[0, 1, 1, 0, 2, 2, 3, 4, 1, 0]
[0, 4, 1, 0, 3, 2, 2, 2, 1, 0]