최대부분 증가수열

선생님 코드

import sys
sys.stdin = open("input.txt", "rt")

n = int(input())
arr = list(map(int, input().split()))
arr.insert(0,0)

dy = [0]*(n+1)
dy[1] = 1 # 첫번째 숫자는 앞에 아무것도 없으므로
res = 0

for i in range(2, n+1):
   max = 0
   for j in range(i-1, 0, -1): # i 바로 앞에서 부터 1 까지 돈다
       if arr[j]<arr[i] and dy[j] > max: # 마지막 항의 바로 앞에서부터 1까지
           # arr항의 바로 앞의 숫자를 찾는 행위!!
           max = dy[j]
   dy[i] = max+1
   if dy[i] > res: 
       res = dy[i]
print(res)

첫번째 숫자는 앞에 아무 것도 없으므로 1로 초기화 해 놓는다.(증가수열의 크기가 1)

2부터 i 바로 앞에서부터 1까지 맨 마지막 숫자와 i를 비교하여
i 보다 작은 수를 중 가장 큰 수를 찾는다
그리고 +1 해 주어 arr[i] 을 초기화 해준다.

마지막으로 증가수열의 크기가 가장 큰 것을 res 에 계속 초기화하여
출력한다.