[백준/파이썬] 11054 가장 긴 바이토닉 부분 수열

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

---

알고리즘

• 다이나믹프로그래밍

문제풀이

원래의 수열에서 증가하는 수열 길이는 [1,2,2,1,3,3,4,5,2,1],
감소하는 수열 길이는 [1,5,2,1,4,3,3,3,2,1]이다.
예시의 경우, 1,2,3,4,5 / 5,2,1 총 길이 8에서 중복된 5를 한번 빼주면 7이 나온다.

array=[1,5,2,1,4,3,4,5,2,1]
reverse_array=[1,2,5,4,3,4,1,2,5,1]

d_front=[1,2,2,1,3,3,4,5,2,1]
d_rear=[1,2,3,3,3,4,1,2,5,1]

여기서 d_front와 d_rear의 뒤부터 더해가면 된다.

내가 틀린 코드
import copy

n=int(input())
array=list(map(int, input().split()))
array_copy=copy.deepcopy(array)
d_front=[1]*n
for i in range(1, n):
  for j in range(i):
    if array[j]<array[i]:
      d_front[i]=max(d_front[i], d_front[j]+1)
print(d_front)

array_copy.reverse()
d_rear=[1]*n
for i in range(1, n):
  for j in range(i):
    if array_copy[j]<array_copy[i]:
      d_rear[i]=max(d_rear[i], d_rear[j]+1)
print(d_rear)

print(array)
print(array_copy)

result=1
for i in range(n-1):
  if (n-1)%2==0:
    if array[i]==array_copy[n-2-i]:
      result=max(result, d_front[i]+d_rear[n-2-i]-1)
    else:
      result=max(result, d_front[i]+d_rear[n-2-i])
    print("even"+str(result))
  else:
    if i<((n-1)//2):
      if array[i]==array_copy[n-1-i]:
        result=max(result, d_front[i]+d_rear[n-1-i]-1)
      else:
        result=max(result, d_front[i]+d_rear[n-1-i])
      print("if"+str(result))
    else:
      print(array[i], array_copy[n-2-i])
      if array[i]==array_copy[n-2-i]:
        result=max(result, d_front[i]+d_rear[n-2-i]-1)
      else:
        result=max(result, d_front[i]+d_rear[n-2-i])
      print("else"+str(result))

print(result)

소스코드

n=int(input())
array=list(map(int, input().split()))
reverse_array=array[::-1]

d_front=[1]*n
d_rear=[1]*n

for i in range(n):
  for j in range(i):
    if array[j]<array[i]:
      d_front[i]=max(d_front[i], d_front[j]+1)
    if reverse_array[j]<reverse_array[i]:
      d_rear[i]=max(d_rear[i], d_rear[j]+1)

result=[0]*n
for i in range(n):
  result[i]=d_front[i]+d_rear[n-1-i]-1

print(max(result))