[백준/BOJ] - 11503번 python 풀이 - DP

---

Key Point

1. dp를 사용하는 문제인데, dp 배열에 수열의 순서의 최댓값에 해당하는 값을 적는 알고리즘을 적용.

2. 모든 dp는 1로 초기화하고 위 예시를 기준으로 보면 

10은 첫번째 수이므로 1

두번째 수 20은 앞서 있는 값보다 크기 때문에 dp 값 + 1 하여 2

세번째 수 10은 앞서있는 값 10, 20보다 크지 않으므로 dp값 변동 x (1)

네번째 수 30은 앞서있는 값 10, 20, 10보다 각각 크다. 

각 case 마다 dp[idx]의 값+1과 네번째수 담당 dp 부분과 비교하여 큰 값을 해당 dp에 저장한다.

이런 방식으로 진행하면 수열의 길이의 최댓값이 저장 될 것이다.

---

import sys
input = sys.stdin.readline
n = int(input())
d = [1] * n
num = list(map(int, input().split()))
for i in range(n):
    for j in range(i):
        if num[i] > num[j]:
            #최댓값을 구하는 것
            d[i] = max(d[i], d[j]+1)

print(max(d))