99클럽 코테 스터디 32일차 TIL + DP

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

import sys
input = sys.stdin.readline

n = int(input())
S = list(map(int, input().split()))
reversedS = list(reversed(S))

incDp = [1] * n
decDp = [1] * n
dp = [0] * n
for i in range(n):
    for j in range(i):
        if S[i] > S[j]:
            incDp[i] = max(incDp[i], incDp[j]+1)

        if reversedS[i] > reversedS[j]:
            decDp[i] = max(decDp[i], decDp[j] + 1)

decDp = decDp[::-1]
for i in range(n):
    dp[i] = incDp[i] + decDp[i] - 1

print(max(dp))

• 가장 긴 바이토닉 부분 수열은 LIS를 두번 사용해 가장 긴 증가하는 부분수열, 가장 긴 감소하는 부분수열을 구한다.
  • 가장 긴 감소하는 부분수열은 idx가 증가할수록 감소해야 하기 때문에 한번의 for문으로 구하기 위해 reverse 된 리스트로 구해야 한다.
• 감소수열과 증가수열의 합이 최대인 idx의 값을 기준으로 가장 긴 바이토닉 수열을 구할 수 있다.
• reversed함수를 사용하거나 list[::-1]로 리스트를 뒤집을 수 있다.
• -1을 해주는 이유는 기준되는 값을 2번 더해주기 때문에 한번 뺴주어야 한다.