가장 긴 증가하는 부분 수열

❓문제

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

❗문제 정리

• 수열은 증가하는 수열이다!
• 수열의 길이를 저장하는 dp 테이블을 정의.

1. array[i]가 어떤 증가 부분 수열의 마지막 값이 되기 위해서는 array[i]가 추가되기 전 증가 부분수열의 마지막 값이 array[i]보다 작아야한다.
2. 가장 긴 증가부분수열의 길이는 array[i]가 추가될 수 있는 증가부분 수열 중 가장 긴 수열의 길이+1

📑코드

n=int(input())#전체 수열의 길이
arr=[0]+list(map(int, input().split()))

dp=[0]*(n+1)
for i in range(0,n+1):
  for j in range(i):
    if arr[i]>arr[j]:#a의 값이 어디에 붙을 수 있는지 확인
      #j인덱스에 붙을 수 있음
      dp[i]=max(dp[i],dp[j]+1)
print(max(dp))

📝코드 설명

n=int(input())#전체 수열의 길이
arr=[0]+list(map(int, input().split()))

전체 수열의 길이 n과 수열을 입력받는다.
이때, 0을 추가해주어 인덱스 이동을 쉽게 한다.(dp테이블도 0부터 시작!)

dp=[0]*(n+1)

가장 긴 수열의 길이를 저장하는 dp테이블을 정의하고 0으로 초기화한다.

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

i가 j보다 큰 경우 dp테이블 값이 이미 dp에 있던 값과 (가장 긴 수열의 길이 +1) 값 중 큰것으로 업데이트 된다.

print(max(dp))

최고로 긴 수열의 길이를 출력하라 하였으므로, dp에서 가장 큰 값을 출력한다.

예제1
1. 초기 상태

2. for문 돌면서 dp 업데이트
   
   
   

🎖제출 결과

💡insight

나무위키 - 최장 증가 부분 수열