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

생각외로 되게 간단하게 풀렸다.

역시 커피한잔하면서 백준문제풀면 훨씬 나은 듯 하다.

점화식이 항상 깔끔하게 한줄식으로만 나오지 않을수도 있다는 교훈을 얻게 해준 문제였다.

# n 입력

n = int(input())

# a 입력

a = list(map(int, input().split()))

# dp 설계

dp = [

　0 for _ in range(1000)

]

# 초기설정

dp[0] = 1

# dp 채워넣기

for i in range(1, n):

　# dp 최댓값 설정

　M = 0

　for j in range(i):

 

　　# 이전까지 더 작은 수 중에 dp 값이 더 큰수 를 찾으면

　　if a[j] < a[i] and dp[j] > M:

 

　　　# dp 최댓 값 갱신

　　　M = dp[j]

 

　# 채워넣기

　dp[i] = M + 1

# 출력

print(max(dp))