[백준 11053 가장 긴 증가하는 부분 수열 문제] PYTHON

 

 

1. 수열을 배열화

2. 수열과 같은 크기의 배열 DP를 생성

3. 수열배열과 같은 index의 DP에 증가하는 부분수열의 길이의 최댓값을 저장

4. 결국 cost가 낮으면 DP배열의 index를 체크해 자신 이하의 값을 가지고 있으면 +1한것을 저장

 

 

N = int(input())
cost=list(map(int, input().split()))
dp=[ 1 for _ in range(N)]

for i in range(1,N):
    for j in range(0,i):
        if(cost[j]<cost[i]):
            if(dp[j]>=dp[i]):
                dp[i]=dp[j]+1
print(max(dp))