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

 

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

문제 링크 : https://www.acmicpc.net/problem/11053

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

 

• 기본적인 LIS 문제이다. 따라서 DP 로 접근할 수 있다 

 

# 코드

import sys

n = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split()))
dp = [1 for _ in range(n + 1)]

for i in range(1, n):
    for j in range(i):
        if seq[i] > seq[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))