문제

풀이

이 문제는 lis 알고리즘으로 해결가능하고
lis 관련링크는 ----> lis 알고리즘 설명!!!

lis알고리즘으로 구현 해보자면

코드

#입력
# 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
# 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
#sample
# 6
# 10 20 10 30 20 50

#점화식
#dp[i] = dp[j] + 1 (if j < i)
#2중 for문으로 돈다 생각하면 됨
import sys

N = int(input())

arr = list()
arr = list(map(int, sys.stdin.readline().split()))

dp = [1] * N

#바텀업으로 채우기
for i in range(1,N):
  for j in range(i):
    if(arr[j] < arr[i]):
      dp[i] = max(dp[i], dp[j]+1)

print(max(dp))