❗️[알고리즘]최대 부분 증가 수열

문제

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다.

▣ 입력설명
첫째 줄은 입력되는 데이터의 수 N(2≤N≤1,000, 자연수)를 의미하고, 둘째 줄은 N개의 입력데이터들이 주어진다.

▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

입력예제1

8
5 3 7 8 6 2 9 4

출력예제1

4

[해설코드]

n=int(input())
arr=list(map(int,input().split()))
#한 칸씩 오른쪽으로 밀기
arr.insert(0,0)
dp=[0]*(n+1)
dp[1]=1
res=0
for i in range(2,n+1):
	max=0
    for j in range(i-1,0,-1):
    	if arr[j]<arr[i] and dp[j]>max:
        	max=dp[j]
    dp[i]=max+1
    if dp[i]>res:
    	res=dp[i]

1. dp테이블은 입력 받은 값들의 해당하는 수열의 최대길이를 의미
2. 직관적으로 보기 쉽도록 인덱스값을 오른쪽으로 한 칸 씩밀어준다.
3. 예를 들어 입력예제1에서 arr[4]의 값인 8은 arr[1],arr[2],arr[3]보다 더 큰 수 이므로 앞에 dp[1]=1,dp[2]=1,dp[3]=2 중 가장 큰 값 뒤에 수열을 붙이고 자기자신(8)을 추가하므로 +1를 해준다.
4. 출력값은 dp배열 중 가장 큰 수를 출력.