[Python] 백준 11053 - 가장 긴 증가하는 부분 수열

백준 11053 - 가장 긴 증가하는 부분 수열

문제

코드

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
length = [0] * n

for i in range(0, n):
    for j in range(i):
        if arr[i] > arr[j]:
            if length[i] < length[j]:
                length[i] = length[j]
    length[i] += 1

print(max(length))

해설

1. 입력: arr = list(map(int, input().split()))

2. DP이용 => 각 수마다 수열 최대길이를 배열에 저장
   어떤 수 이전의 수열 최대길이를 모두 비교!
   이때 수열의 값은 더 커야함

3. 출력: print(max(length))