greentea31's Note

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

풀이 과정

D[i] => A[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이라고 하면,

이렇게 A[i]에 따른 D[i]를 고려해볼 수 있으며,

D[i] = max(D[J]) + 1 (j < i, A[j] < A[i]) 이 성립함을 알 수 있다.

소스 코드

import sys

N = int(sys.stdin.readline())

A = list(map(int, sys.stdin.readline().split()))
A.insert(0, 0)

d = [1 for _ in range(len(A))]

for i in range(2, len(A)):
    checkMaxLength = 0
    for j in range(1, i):
        if A[j] < A[i]:
            checkMaxLength = max(checkMaxLength, d[j])
        d[i] = checkMaxLength + 1

print(max(d))