가장 긴 증가하는 부분 수열 (LIS)

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

view raw 백준 가장 긴 증가하는 부분 수열 hosted with ❤ by GitHub

1 단계는 다이나믹 프로그래밍만 사용하면 됨. - 자기보다 작은 인덱스이며 자신의 값보다 작은 값들 중에서 dp 값이 가장 큰 놈에게 1 더해준 값이 자신의 dp 값이 된다.