[#알고리즘/Dynamic Programming/[백준]11053번: 가장 긴 증가하는 부분 수열(python)]

Question

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

Solution

수열의 각 원소에 기본적으로 1씩 증가시킨다. 이때, 자신 이전의 원소 중, 자신보다 작은 원소의 길이 중 가장 큰 길이에 +1을 한다. 수열의 끝 원소까지 길이 설정을 끝냈다면, 가장 큰 길이를 출력한다.

Code

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
d = [0] * 1001

for i in range(N) :
    for j in range(i) :
        if arr[i] > arr[j] and d[i] < d[j] :
            d[i] = d[j]
    d[i] += 1
    
print(max(d))