11053번: LIS 가장 긴 증가하는 부분수열 (DP) - Fastcampus

www.acmicpc.net/problem/11053

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

# dp[i] = i번째 수를 마지막 원소로 가지는 부분수열의 최대길이
#         (j번째 수 = i번째 수와 연결되는 앞 수열의 작은 수)
#
# dp[i] = max(dp[j]) + 1, j < i
#
# nums  = [10, 20, 10, 30, 20, 50]
#
# dp[0] = {10} = 1
# dp[1] = {10,20} = 2
# dp[2] = {10} = 1
# dp[3] = {10,30} or {..,20,30} or {..,10,30} = max(dp[0],dp[1],dp[2]) + 1 = 3
# dp[4] = max(dp[0],dp[2]) + 1 = 2
# dp[5] = max(dp[0],dp[1],dp[2],dp[3],dp[4]) + 1 = 4

def run(N, a):
    dp = [1] * N

    for i in range(1, N):
        for j in range(0, i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)


N = int(input())
nums = list(map(int, input().split()))

length = run(N, nums)
print(length)