[백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬)

문제) 백준 - 동적 계획법 (Dynamic programming) - 가장 긴 증가하는 부분 수열

-> www.acmicpc.net/problem/11053

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

 

각 숫자로 만들 수 있는 가장 긴 증가하는 부분 수열의 길이를 저장할 length 리스트를 선언한다. 각 숫자(i)들을 차례대로 순회(0 ~ n)하면서 해당 숫자(i)보다 작고 가장 긴 증가하는 부분 수열을 찾아 그 길이에서 1을 더한다.

 

 

소스 코드)

import sys
input = sys.stdin.readline

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

length = [0] * n
for i in range(n):					#모든 숫자 순회
    for j in range(i):					#해당 숫자 이전까지 탐색
        if num[j] < num[i] and length[j] > length[i]:
            length[i] = length[j]
    length[i] += 1

print(max(length))