파이썬 백준 11053번 : 가장 긴 증가하는 부분 수열

문제

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

 

 

풀이

다이나믹 프로그래밍으로 해결했다.

1. dp테이블의 모든 값을 1로 초기화 한다.

2. 수열의 수를 순회한다.

2-1. 그 이전의 수가 자신보다 작을 경우

2-2 . 자신의 dp값과 해당 수의 dp값 +1 중 큰 값으로  dp테이블을 업데이트 한다.

3. dp테이블에서 가장 큰 값을 출력한다. 

import sys

n = int(sys.stdin.readline())
sequence = list(map(int, sys.stdin.readline().split()))
dp = [1] * (n+1)

for i in range(len(sequence)):
    for j in range(i): #이전까지의 수가 현재보다 작으면 dp테이블 값 조회
        if sequence[j] < sequence[i]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))