[백준 단계별 풀이 - 동적계획법] #11054 가장 긴 바이토닉 부분수열

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

코드

# 수열 : 1 5 2 1 4 3 4 5 2 1

# 증가 : 1 2 2 1 3 3 4 5 2 1 # 왼쪽에서 오른쪽으로 진행. 왼쪽 수열 중에서 해당 숫자보다 작은 숫자가 있다면
                             # 그때의 인덱스의 증가 수열 값 + 1을 저장 (가장 큰 값을 택함)
# 감소 : 1 5 2 1 4 3 3 3 2 1 # 오른쪽에서 왼쪽을 진행. 똑같음.
# 합-1 : 1 6 3 1 6 5 6 7 3 1


N = int(input())
A = list(map(int, input().split()))

inc = [1 for _ in range(N)]
dec = [1 for _ in range(N)]
ans = [0 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            inc[i] = max(inc[j] + 1, inc[i])

for i in range(N-1,-1, -1):
    for j in range(N-1, i-1,-1):
        if A[i] > A[j]:
            dec[i] = max(dec[i], dec[j]+1)
    ans[i] = inc[i] + dec[i] - 1
    # numpy가 아니라 그냥 python에서 하는 list 의 sum은 수열이 합쳐짐(길어짐)

print(max(ans))