[BaekJoon] 11054번 : 가장 긴 바이토닉 부분 수열 (Python)

1일 1문제 140일차!

140일차의 문제는 백준의 가장 긴 바이토닉 부분 수열 입니다.

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

Solution

import sys
r = lambda : sys.stdin.readline()

def _get_seq_len(a):
    dp = [1 for _ in range(len(a))]
    rev_dp = [1 for _ in range(len(a))]
    for i in range(len(a)):
        dp[i] = 1
        for j in range(i, -1, -1):
            if a[i] > a[j] and dp[i] <= dp[j]:
                dp[i] = dp[j] + 1
    for i in range(len(a)-1, -1, -1):
        rev_dp[i] = 1
        for j in range(i, len(a)):
            if a[i] > a[j] and rev_dp[i] <= rev_dp[j]:
                rev_dp[i] = rev_dp[j] + 1
    print(max([i+j for i,j in zip(dp, rev_dp)])-1)
    
N = int(r())
seq = list(map(int, r().split()))
_get_seq_len(seq)

SOMJANG/CODINGTEST_PRACTICE