1965번 파이썬

처음에 p리스트를 1로 초기화한 이유는 본인의 상자만 포함할 경우 한개이기 때문이다.

그 다음 1부터 n까지 반복문을 돌려서 i번째 전까지 상자 중 최대가 되는 것을 찾기 위해서 다시 한번 반복문을 1부터 i-1까지 돌린다. 이때 p[i]번째가 max(p[i],p[k]+1)인 이유는 p[i]에는 계속 새로운 값이 저장되고 그 값이 최대인 경우를 가리기 위해서이다.

예를 들어 1,3,1,5가 있을때 i가 5일 경우 k가 3의 인덱스일때 p[i]에는 최댓값 3이 저장되고 이후 1이의 인덱스에 올때 이미 최댓값 3이 저장되어 있다.

import sys
input = sys.stdin.readline
n=int(input())
ary = list(map(int,input().split()))
p = [1 for _ in range(n+1)]

for i in range(1,n+1):
  for k in range(1,i):
    if ary[k-1] < ary[i-1]:
      p[i]=max(p[i],p[k]+1)
print(max(p))