IT-garden

문제

수열 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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=list(map(int,input().split()))

dp=[1] * n
dp2=[1] * n
for i in range(n): # 앞에서부터 부분 증가수열 개수
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]+1:
            dp[i] = dp[j]+1

for i in range(n-1,-1,-1): # 뒤에서부터 부분 증가수열 개수
    for j in range(n-1,i-1,-1):
        if a[i]> a[j] and dp2[i] < dp2[j]+1:
            dp2[i] = dp2[j]+1

li=[0] * n
for i in range(n):
    li[i]=dp[i]+dp2[i]-1

print(max(li))

가장 긴 부분 수열을 앞에서부터 실행하고 뒤에서부터 실행합니다.
두 배열의 값을 합치고 1을 뺍니다.(자기자신의 길이도 포함하기 때문에)
두 배열의 값을 합친 것 중 가장 큰 값을 출력합니다.

백준 알고리즘 11054번 : www.acmicpc.net/problem/11054