problem-11054

과정
1. 오름차순 -> 내림차순 순서이기 때문에, dp를 오름차순용과 내림차순용으로 두개 만듬
2. 오름차순의 경우, 최장부분수열의 길이 dp 구하면 된다.
3. 내림차순의 경우, 오름차순의 마지막 값부터 수열의 마지막 값까지 안에서 최장내림차순부분수열의 길이를 구해야한다.
4. 따라서 내림차순의 dp를 구할 때는 먼저 오름차순dp에 포함된 수열을 제외하여 새로운 수열을 정의하고, 그에 따른 부분 dp를 새로 정의한다.
5. 새롭게 정의한 수열에 대해서 dp 값을 구한후, 최종 내림차순 dp에 추가한다 (이때 모자란 부분은 0으로 추가한다)
6. pivot을 i라고 한다면, dp_ac[i]+max(dp_dec[i])-1 이다. (겹치는 것 1개 빼고, dp_dec에서 최댓값을 더함)

import sys
n=int(input())
a=[0]
temp=list(map(int,input().rstrip().split()))
for i in temp:
    a.append(i)

dp_ac = [1 for i in range(n+1)]
dp_dec = [[0]*(n+1)]

for i in range(1,n+1):
    for j in range(1,i):
        if a[i]>a[j]:
            dp_ac[i]=max(dp_ac[i],dp_ac[j]+1)
  
        
for i in range(1,n+1):
    t_list = a[i:]
    t_dp = [1 for z in range(len(t_list))]
    for j in range(0,len(t_list)):
        for k in range(0,j):
            if t_list[j]<t_list[k]:
                t_dp[j]=max(t_dp[j],t_dp[k]+1)
    dp_dec.append([0]*i+t_dp)


ans=-1
for i in range(1,n+1):
    ans=max(ans,dp_ac[i]+max(dp_dec[i])-1)
print(ans)
                

time: 100분