이번 문제는 다이나믹 프로그래밍으로 해결하였다. 접근 방법은 수열을 순회하며 현재 수보다 이전에 있는 수 중에 더 큰 수가 있을 경우 dp배열의 현재 위치를 갱신하는 방식이다. 점화식은 dp[i]=max(dp[i], dp[j]+1)가 된다.

• n을 입력받는다.
• a를 입력받는다.
• dp를 1 n개로 초기화한다.
• n만큼 반복하는 i에 대한 for문을 돌린다.
  -> i만큼 반복하는 j에 대한 for문을 돌린다.
  --> 만약 a[j]가 a[i]보다 더 크다면 dp[i]를 dp[i]와 dp[j]+1 중 더 큰 값으로 갱신한다.
• dp에서 가장 큰 수를 출력한다.

Code

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