[11053] 가장 긴 증가하는 부분 수열 (Python)

[문제]

https://www.acmicpc.net/problem/11053

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

---

알고리즘 분류는 다이나믹 프로그래밍 입니다.

A	10	20	10	30	20	50
num	1	2	1	3	2	4

부분수열의 수를 num이라 했을 때, 값을 비교한 뒤 num을 늘려줍니다.

이 중 가장 큰 값(max)를 출력하면 됩니다.

---

[코드]

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
num = [1] * N

for i in range(1, N):
    for j in range(i):
        if A[j] < A[i] and num[i] < num[j] + 1:
            num[i] = num[j] + 1
            
print(max(num))