[동적 계획법][Bottom-Up] - 최대 부분 증가 수열

n = int(input())
arr = list(map(int,input().split()))
arr.insert(0,0)
dp = [0] * (n+1)
dp[1] = 1
res = 0

for i in range(2, n+1):
    MAX = 0
    #해당 기준점이 되는 부분의 바로 앞부터 전체 다 돌아가며 확인을 위한 범위
    for j in range(i-1, 0, -1):
        if arr[i] > arr[j] and dp[j]>MAX:
            MAX = dp[j]
    dp[i] = MAX+1
    if dp[i] > res:
        res = dp[i]
print(res)

---

n = int(input())
arr = list(map(int,input().split()))
arr.insert(0,0)
dp = [0] * (n+1)
dp[1] = 1
res = 0
for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

---

• 투포인터를 사용해서도 풀 수 있을 것 같다. 한 번 시도해봐야겠다.