[Python] 백준(BOJ) 11053번: 가장 긴 증가하는 부분 수열 - dp

문제

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

풀이

LIS(Longest Increasing Subsequence)를 구하는 문제

왼쪽부터 하나씩 돌면서

나보다 왼쪽에 있으면서 나보다 크기가 작은 애들중 가장 dp[i]가 큰 애에 1을 더해주면 된다. 

import sys

n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split(" ")))
dp = [0 for _ in range(n)]

for i in range(len(numbers)):
    for j in range(len(numbers[:i])):
        if numbers[i] > numbers[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1

print(max(dp))