백준: 11054 가장 긴 바이토닉 부분 수열

문제

11054번: 가장 긴 바이토닉 부분 수열

 

문제 풀이

 이 문제는 11053 가장 긴 증가하는 부분 수열, 11722 가장 긴 감소하는 부분 수열를 이해하고 있다면 쉽게 풀 수 있다.  특정 지점을 선택하였을 때, 증가하는 부분과 감소하는 부분의 합이 가장 큰 경우를 반환하면 된다.

 

코드

from sys import stdin

if __name__ == '__main__':
    n = int(stdin.readline())
    nums = list(map(int, stdin.readline().split()))

    forward = [1] * n
    backward = [1] * n
    max_len = 0

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                forward[i] = max(forward[i], forward[j] + 1)

            if nums[n - j - 1] < nums[n - i - 1]:
                backward[n - i - 1] = max(backward[n - i - 1], backward[n - j - 1] + 1)

    for f_cnt, b_cnt in zip(forward, backward):
        cur_len = f_cnt + b_cnt
        max_len = cur_len if cur_len > max_len else max_len

    print(max_len - 1)