백준 11053 - 가장 긴 증가하는 부분 수열

문제.

풀이.

첫번째 위치부터 수열의 길이의 최댓값을 저장하고

자기 자신보다 작은 숫자들 중 가장 큰 길이를 자기 위치에 넣고 +1을 하고 dp의 최댓값을 출력하면 된다.

 

소스코드.

import sys

A = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split()))
dp = [0] * A
for i in range(A):
    for j in range(i):
        if seq[i] > seq[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
print(max(dp))