가장 긴 바이토닉 부분 수열

백준 11054

이 문제는 동적 계획법으로 푸는 문제인데 증가 뿐 아니라 감소하는 부분도 생각해줘야한다.

n = int(input())
arr = list(map(int, input().split()))
dp1 = [1 for _ in range(n)]
dp2 = [1 for _ in range(n)]

for i in range(1, len(arr)):
    for j in range(i):
        if arr[j] < arr[i]:
            dp1[i] = max(dp1[i], dp1[j]+1)

for i in range(len(arr)-1, 0, -1):
    for j in range(len(arr)-1, i, -1):
        if arr[j] < arr[i]:
            dp2[i] = max(dp2[i], dp2[j]+1)

dp = []
for i in range(len(arr)):
    dp.append(dp1[i]+dp2[i])
print(max(dp)-1)

앞에서부터 증가하는 수열, 뒤에서부터 증가하는 수열(감소)을 구해서 수열을 합한다음 가장 큰 값 즉 기준이 되는 값이 중복되므로 1을 빼주면 된다.

추가)
리스트 두개의 각 자리의 합을 새로운 리스트에 저장하는 방법을 한 줄의 코드로 구현하면 다음과 같다.

dp = [dp1[i]+dp2[i] for i in range(n)]

참고
두 배열의 각 자리의 합 리스트