11722 가장 긴 감소하는 부분 수열 [python]

순차적으로 각 수열이 하나식 최대긴수열을 갖는방식을 저장하면서 문제를 해결하는 구조로 풀었다.

 

n = int(input())
arr = list(map(int, input().split()))
cache = [1] * n

for i in range(1, n):
    for j in reversed(range(i)):
        if arr[i] < arr[j] and cache[i] <= cache[j]:
            cache[i] = cache[j] + 1
print(max(cache))