[백준][동적 계획법1] 11053. 가장 긴 증가하는 부분 수열LIS(파이썬/Python)

#11053

import sys
input = sys.stdin.readline

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

#DP를 위한 1차원 DP테이블 초기화
dp = [1]*n

#가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행.
for i in range(1,n):
    for j in range(0,i):
        if a_list[j] < a_list[i]:
            dp[i] = max(dp[i],dp[j] +1 )# 1 
print(max(dp))

# 1 DP의 경우 중복된 함수를 불러서 쓰는 것 대신 쓴 값을 저장해서 쓰는 방식이기 때문에 이를 위해서 이미 쓴 값인지를 확인