[Python]동적계획법 백준 11054

   문제

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

이전문제와 비슷한 문제다.

이전문제는 오름차순만 구했다면 이번문제는 내림차순도 구해주어 

두결과값의 합에서 1을 뺀값의 최대값이 정답이 될것이다.

내림차순은 반대쪽에서 부터 시작하는 오름차순으로 구현하였다.

import sys
 
n=int(sys.stdin.readline())
bitonic=list(map(int, sys.stdin.readline().split()))
ascending=[0 for _ in range(n)] #오름차순
descending=[0 for _ in range(n)] #내림차순
for i in range(n):#오름차순 긴수열
    max_value=0
    for j in range(i):
        if bitonic[i]>bitonic[j]:
            if max_value<ascending[j]:
                max_value=ascending[j]
    ascending[i]=max_value+1
 
for i in range(n-1,-1,-1):#반대쪽에서 시작하는 오름차순 긴수열
    max_value = 0
    for j in range(n-1,i,-1):
        if bitonic[i]>bitonic[j]:
            if max_value<descending[j]:
                max_value=descending[j]
    descending[i]=max_value+1
 
 
 
result=[ascending[i]+descending[i]-1 for i in range(n)]#오름차순과 내림차순 수열길이의 합
print(max(result))