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

https://www.acmicpc.net/problem/11054
시간 1초, 메모리 256MB
input :

• N (1 ≤ N ≤ 1,000)
• Ai (1 ≤ Ai ≤ 1,000)

output :

• A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이

조건 :

• 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열
• {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

---

증가하는 부분증가 수열, 감소하는 부분증가 수열의 dp 값을 두개 구해서 그 둘을 더하면 길이를 구해낼 수 있지 않을 까?

• 증가하는 부분증가 수열.

dp_add = [1] * n

for i in range(n):
    for j in range(i):
        if data[i] > data[j]:
            dp_add[i] = max(dp_add[i], dp_add[j] + 1)

• 감소하는 부분증가 수열.

dp_subtract = [1] * n
data.reverse()
for i in range(n):
    for j in range(i):
        if data[i] > data[j]:
            dp_subtract[i] = max(dp_subtract[i], dp_subtract[j] + 1)

dp에 넣어두는 값을 보면 마지막에 자기자신도 포함이 된다. 그렇기 때문에 dp 리스트를 다시 reverse 해서 더해 줄 때는 1을 빼줘야 한다.
정답 코드 :

import sys

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
dp_add = [1] * n

for i in range(n):
    for j in range(i):
        if data[i] > data[j]:
            dp_add[i] = max(dp_add[i], dp_add[j] + 1)

dp_subtract = [1] * n
data.reverse()
for i in range(n):
    for j in range(i):
        if data[i] > data[j]:
            dp_subtract[i] = max(dp_subtract[i], dp_subtract[j] + 1)

dp_subtract.reverse()
for idx, item in enumerate(dp_add):
    dp_subtract[idx] += item

print(max(dp_subtract) - 1)