[백준] 11053: 가장 긴 증가하는 부분 수열

DP

가장 긴 증가하는 부분 수열

수열의 길이가 1000까지이기 때문에 O(n^2)의 알고리즘을 사용해서 문제를 풀 수있습니다.
나무위키 참조

원소가 1개라도 부분 수열이 1이므로 DP리스트는 1로 초기화해 줍니다.
그리고 현재 비교하는 수 보다 더 작은 수 들이 왼쪽에 있다면 왼쪽에 있는 디피값에 1을 더한 값과 현재 값을 비교하여 가장 큰 값을 갱신해줍니다.
그리고 디피 값의 최댓값을 출력하면 됩니다 .

import sys
n = int(input())
lst = list(map(int, input().split()))
dp = [1] * (n)
for i in range(len(lst)):
	for j in range(i):
		if lst[i] > lst[j]:
			dp[i] = max(dp[i], dp[j]+1)
print(max(dp))