📚 11053 - 가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열

 

1. dp[i]의 값을 1로 초기화
2. 현재 위치보다 이전에 있는 원소의 값이 작은지 확인한다. (크거나 같으면 가장 긴 증가하는 부분 수열이 될 수 없다.)
3. 작다면, 현재 위치의 이전 숫자 중, dp값에 + 1을 하여 현재 위치 dp 값과 비교한다.
4. 그 중 최대값을 구한다.

 

예시를 보면 이와 같다.

arr	10	70	80	20	30	40	50	90
dp	1	2	3	2	3	4	5	6

 

n = int(input())

dp = [1] * (n + 1)

arr = list(map(int, input().split() ))


for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

 

실행 결과

 

참고 내용 : https://seohyun0120.tistory.com/entry/%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4LIS-%EC%99%84%EC%A0%84-%EC%A0%95%EB%B3%B5-%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC