✅ BOJ 11054 - DP, LIS

가장 긴 바이토닉 부분 수열

뭘 구함?
수열 하나 주고, 증가하다가 감소하는 흐름 중에 제일 긴 거 하나만 찾으면 됨. 전부 찾는 거 아님.

아이디어
부분 수열 전부 만들면 시간 터짐. DP로 간다.

• 왼쪽에서 오는 LIS (가장 긴 증가 부분 수열)
• 오른쪽에서 오는 LDS (가장 긴 감소 부분 수열)
  LIS는 그대로, LDS는 수열 뒤집어서 LIS처럼 돌리고 다시 뒤집으면 됨.

핵심 흐름

• LIS[i] = i에서 끝나는 증가 흐름 길이
• LDS[i] = i에서 시작하는 감소 흐름 길이
• 각 인덱스에서 LIS + LDS - 1 해서 최대값 찾으면 끝.

이게 전부임. DP는 이중 for문으로 O(N²)라 길이 1000이면 충분히 통과한다.

---

# dp,LIS,LDS
import sys
input=sys.stdin.readline

def find_LIS(seq,n):
    LIS=[1]*n

    for i in range(n):
        for j in range(i):
            if seq[j]<seq[i]:
                LIS[i]=max(LIS[i],LIS[j]+1)
                
    return LIS

def main():
    n=int(input())
    seq=list(map(int,input().split()))

    LIS=find_LIS(seq,n)
    LDS=find_LIS(seq[::-1],n)[::-1]

    result=0
    for i in range(n):
        length=LIS[i]+LDS[i]-1
        result=max(result,length)
    print(result)
    
if __name__=="__main__":
    main()