백준 | [파이썬 Python] 11053 가장 긴 증가하는 부분 수열

---

 

코드

n=int(input())
dy=[0]*1001
ls=list(map(int,input().split()))
ls.insert(0,0)

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

print(max(dy))

 

 

설명

dynamic list에는 해당 칸에 가장 큰 증가수열의 값을 넣습니다.

앞의 숫자보다 크다면 증가 수열을 만들 수 있으므로 해당 dy list 안에 있는 가장 큰 증가수열에 +1을 해주면 됩니다

 

백준에 있는 예시인 10 20 10 30 20 50

20의 경우 앞의 10보다 크기에 10이 만들 수 있는 가장 큰 증가수열 1에 +1을 더해줍니다

30의 경우 앞의 10과 20보다 크기에 첫 번째 루프의 경우 10이 가진 가장 큰 증가 수열 1에 +1 dy[3]은 2

두 번째 루프의 경우 20이 가진 가장 큰 증가 수열 2에 +1 dy[3]은 3이 됩니다