가장 큰 증가 부분 수열 풀이

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

백준 알고리즘 기초 1/2 401에서 8번째 - 11055번 가장 큰 증가 부분 수열을 풀어보았다.

 

풀이: 가장 긴 증가하는 부분 수열 코드를 조금 변형했다.

 

C++

 

Python

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

Java