가장 긴 증가하는 부분 수열 ( 11053번 )

https://www.acmicpc.net/problem/11053

 

나의 풀이

import sys

def _main(n, n_list):
    answer = [1] * n
    for i in range(len(n_list)):
        for j in range(i, len(n_list)):
            if n_list[j] > n_list[i]:
                answer[j] = max(answer[j], answer[i] + 1)
    return max(answer)

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

 

시간 복잡도

for i in range(len(n_list)) : 숫자 배열을 순회 ( 선형 시간 복잡도 )
    for j in range(i, len(n_list)) : 비교를 위한 숫자 배열을 순회 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )