백준 11053. 가장 긴 증가하는 부분 수열

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

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

---

key 를 기준으로 증감을 판별해야 하므로 이중 반복문이 필요할 것이라 판단했다.

그리고 총 수열의 길이가 1일 때부터 n일 때까지를 동적 계획법으로 구상하면 새로운 수가 수열에 포함될때마다 증가하는 부분수열을 구성할 수 있는지 판단하면 된다.

따라서 최장 길이를 담는 배열을 dp라고 할 때, 

dp[i]만큼의 수열에서 a[i]번째 항이 부분수열을 이루려면

1) a[*] 번째보다 a[i] 항이 커야 한다.

2) a[*]번째까지의 최대 길이인 dp[*]번째에 +1을 해준다. 다만 이 때, 반복을 통해서 처리할 것이므로 dp[i]가 이미 충분히 긴데 더 작은 걸로 바꿔줄 필요는 없다.

 

n = int(input())
dp = [0] * (n+1)
s = [0] + list(map(int, input().split()))

for i in range(1, n+1):
	for j in range(1, i+1):
		if s[i] > s[j] and dp[i] < dp[j]:
			dp[i] = dp[j]
	dp[i] += 1
print(max(dp))