문제

풀이

1. 값이 1이고 크기가 n인 dp 배열을 선언함.
2. dp에 자신을 포함하여 만들 수 있는 부분 수열의 크기를 저장함.
3. for문을 돌며 현재 값(i)이 이전 값(j)보다 큰지 확인 함.
4. 큰 경우, dp값에 1을 더해주고, 마지막에 dp배열의 최댓값을 print해 줌.

코드

def solution() :
    n = int(input())
    arr = list(map(int, input().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))
solution()