DP 최대선 연결하기

▣ 출력설명
첫 줄에 겹치지 않고 그을 수 있는 최대선의 개수를 출력합니다.

▣ 입력예제 1 

10
4 1 2 3 9 7 5 6 10 8

▣ 출력예제 1
6

 

 

n=int(input())

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

dp=[0]*(n+1)
dp[1]=1
res=0
for i in range(2,n):

    max=0
    for j in range(i-1,0,-1):
        if arr[j]<arr[i] and max<dp[j]:
            max=dp[j]

    dp[i]=max+1
    if(res<dp[i]):
        res=dp[i]

print(res)

정답풀이:부분수열의 갯수를 저장해주는 dp를 초기화 해주고 첫번째 인덱스 하나의 선만 가지니까 

dp[1]=1 로 초기화를 시켜준다. 

2중 for문을 사용하여 현재있는 인덱스의 값보다 작은 이전의 값을들 비교하고 dp의 값중 가장 큰 개수를 가진 

dp를 max로 저장한다. dp[i]에 +=1 를 한다  dp중에 가장 긴 부분수열을 가진 res를 출력한다.