# 11053 가장 긴 증가하는 부분수열 (개념)

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

m = [1]*n

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

print(max(m))

 

- 점화식 헷갈리면 외워두기 

- 만약 나보다 전 인덱스에 나보다 작은 값이 있다면, 그 값을 포함하는 것과 현재 값 중 큰 값 고르기 

 

# 다른 폴이

n = int(input())
answer = list(map(int, input().split()))
dp = [0] * n

for i in range(0, n):
    if i == 0 :
        dp[i] = 1
    else :
        max_dp = 0
        for j in range(0, i):
            if max_dp < dp[j] and answer[j] < answer[i]:
                max_dp = dp[j]
        dp[i] = max_dp+1

print(max(dp))

 

 

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

11053번: 가장 긴 증가하는 부분 수열