728x90
코드
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이 됩니다
