[백준 11053번] 가장 긴 증가하는 부분 수열 파이썬/python

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

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

 

범위가 좁아서 간단한 바텀업 디피로 풀어봤습니다.

반복문 두개 써서 시간 복잡도는 O(N^2) 일듯

 

 

import sys
 
input = sys.stdin.readline
 
n = int(input())
arr = list(map(int, input().split()))
 
dp = [1 for i in range(n)]
 
for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)
 
 
print(max(dp))