[BOJ 11053] 가장 긴 증가하는 부분 수열 (Python)

문제

문제

---

문제 해설

DP를 사용하여 가장 긴 부분 수열을 갱신하는 문제입니다.
일단 부분 문제로 나누자면 각 인덱스i 마다 0부터 i까지 중 가장 긴 수열의 길이가 들어갑니다.

DP를 채우는 방식은 i 이전의 배열을 하나씩 방문하여 seq[j]가 seq[i]보다 작다면 dp[i]와 dp[j]+1(자기 자신을 넣었을 경우)를 비교하면 됩니다.

---

풀이 코드

import sys

input = sys.stdin.readline
n = int(input())
dp = [1] * n
seq = list(map(int, input().split()))

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

---