BOJ #11054 가장 긴 바이토닉 부분 수열

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #11054 가장 긴 바이토닉 부분 수열

문제 풀이

LIS 응용 문제다. i 번째 좌표에 대해 좌측으로부터의 LIS 길이와 우측까지의 LDS 길이를 산출해서 더한 뒤 자기 자신은 두 번 더했으므로 1을 빼면 된다.

• i좌표에 대한 LIS 배열 생성 (좌측에 대한)
• i좌표에 대한 LDS 배열 생성 (우측에 대한)
• i좌표에 대해 LIS[i] + LDS[i] - 1이 최대가 되는 값 출력

python 코드

import sys
input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))
lis = [0 for _ in range(N)]
lds = [0 for _ in range(N)]
for i in range(N):
    b = 0
    for j in range(i):
        if nums[i] > nums[j]:
            b = max(b, lis[j])
    lis[i] = b + 1
for i in range(N - 1, -1, -1):
    b = 0
    for j in range(N - 1, i, -1):
        if nums[i] > nums[j]:
            b = max(b, lds[j])
    lds[i] = b + 1
sol = 0
for i in range(N):
    sol = max(sol, lis[i] + lds[i] - 1)
print(sol)