# 1965 상자넣기

# 가장 긴 증가하는 수열 찾기랑 비슷 

n = int(input()) # n <= 1000 
data= list(map(int,input().split()))

dp = [1]*1001

for i in range(n):
  for j in range(i):
    if data[j] < data[i]:
      dp[i] = max( dp[j]+1, dp[i])

print(max(dp))

 

자기 자신인 상자 1 개는 무조건 넣을 수 있으므로 dp = [1]*1001 로 선언한다. 

만약 나보다 작은 상자를 발견하면, 해당 상자를 나에게 넣는 것과 넣지 않는 것의 크기를 비교해서 더 큰 것을 넣는다. 

 

https://www.acmicpc.net/problem/1965

1965번: 상자넣기