백준 11053 : 문제링크

  • 문제유형 :

    • 탐색

    • 동적 프로그래밍

  • 설명

    • 수열의 크기가 N일 때, 기본적으로 동적 프로그래밍 알고리즘으로 O(N^2)으로 해결

    • D[i]는 array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이

    • 모든 0 <= j < i에 대하여, D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

    • N = 6 일 때

      스크린샷 2020-11-05 오후 9 30 40

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    n = int(input())
    array = list(map, input().split())
    dp = [1] * n

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

    print(max(dp))