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

문제 링크

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

문제 설명

• dp를 사용하는 문제로 dp 배열의 변화는 아래 그림과 같다. ()안에 있는 숫자는 dp 배열 값 의미로 실제 사용되는 값이 아님
  
• 입력받은 seq 배열의 index를 기준으로 index - 1번째 가지 비교하여 현재 seq index보다 작은 값을 가지고 있는 값들 중 가장 큰 값에 + 1을 하여 dp 배열을 교체 한다.
• 그림은 seq 배열의 값이 30 일때를 예시로 든 그림이다. seq[3] 이니 seq[2] ~ seq[0] 중 30보다 작은 값들 중 20의 index인 dp[1]의 2가 가장 크고 그 배열에 값인 2(10, 20)에 30인 현재 값이 추가된 (10, 20, 30)을 만들 수 있기 때문에 2 + 1 인 3이 된다.

코드

n = int(input())

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

for i in range(0, n):
    mx = 0
    for j in range(i - 1, -1, -1):
        if seq[i] > seq[j]:
            if mx < dp[j]:
                mx = dp[j]
        dp[i] = mx + 1

print(max(dp))