[백준][Python] 11053번 가장 긴 증가하는 부분 수열 - 코팩

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

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

풀이

가장 긴 증가하는 부분 수열을 구하는 알고리즘을 LIS(Longets Increasing Subsequence) 알고리즘이라 부릅니다.

dp를 활용하여 문제를 풀어줍니다.

# 11053번 가장 긴 증가하는 부분 수열, Longest Increasing Subsequence
import sys

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

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

print(max(dp))

출력결과