[백준] 11053번 가장 긴 증가하는 부분수열 - dp, LIS

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

11053번: 가장 긴 증가하는 부분 수열

 

LIS 알고리즘 - DP

https://hhiyeon.tistory.com/167

[알고리즘] LIS(Longest Increasing Subsequence) 최장 증가 부분 수열

 

 

백준 풀이

#n = 6
#arr = [10,20,10,30,20,50]
n = int(input())
arr = list(map(int, input().split()))
dp = [1]*n # 리스트로 반복되는 횟수를 저장한다.
for i in range(n):
	for j in range(i):
		if arr[i] > arr[j]:
			dp[i] = max(dp[i], dp[j]+1)

# print(dp)
# 1 2 1 3 2 4
# 10의 길이 1, 20의 길이 2, 10의 길이 ...
print(max(dp))