가장 긴 감소하는 부분 수열 풀이

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

백준 알고리즘 기초 1/2 401에서 9번째 - 11722번 가장 긴 감소하는 부분 수열을 풀어보았다.

 

풀이: 가장 긴 증가하는 부분 수열에서 부등호만 바꿔주면 된다.

 

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