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

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

 

나의 풀이

import sys

def _main(ct, n_list):
    answer = [1] * ct
    answer_re = [1] * ct
    n_list_re = n_list[::-1]

    for idx in range(ct):
        for j_idx in range(idx):
            if (n_list[idx] > n_list[j_idx]):
                answer[idx] = max(answer[idx], answer[j_idx] + 1)
            if (n_list_re[idx] > n_list_re[j_idx]):
                answer_re[idx] = max(answer_re[idx], answer_re[j_idx] + 1)
    answer_re = answer_re[::-1]

    result = 0
    for idx in range(ct):
        result = max(result, answer[idx] + answer_re[idx])
    return (result - 1)

ct = int(sys.stdin.readline())
n_list = list(map(int, sys.stdin.readline().rstrip().split()))
print(_main(ct, n_list))

 

시간 복잡도

for idx in range(ct) : 수열 길이 만큼 순회 ( 선형 시간 복잡도 )
    for j_idx in range(idx) : 현재 index 기준 앞에 수열까지 순회 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )