가장 긴 증가하는 부분 수열 풀이

문제 링크: https://www.acmicpc.net/problem/11053

백준 알고리즘 기초 1/2 400에서 10번째 - 11053번 가장 긴 증가하는 부분 수열을 풀어보았다.

 

풀이: LIS의 이해가 필요하다. https://techblog-history-younghunjo1.tistory.com/295 와 https://youtu.be/CE2b_-XfVDk 를 보면 이해가 될 것이다.

 

C++

 

Python

n=int(input())
arr=list(map(int,input().split()))
dp=[1 for i in range(1001)]
for i in range(1,n):
	for j in range(0,i):
		if arr[j]<arr[i]: dp[i]=max(dp[i],dp[j]+1)
print(max(dp))

Java