[백준/Python3] 11053 가장 긴 증가하는 부분 수열

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

풀이

전체 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제다. dynamic programming을 이용하여 자신과 자신보다 이전에 나온 수열을 비교해 그보다 클 경우 길이를 계속 갱신하는 방법으로 해결할 수 있다.

코드

# Initial
N = int(input())
A = list(map(int, input().split()))
answer = 0

# Make dp table
dp = [1 for _ in range(N)]

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

# Answer
answer = max(dp)
print(answer)