BOJ(가장 긴 증가하는 부분 수열)(11053)

작성일 | In

가장 긴 증가하는 부분 수열

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

for i in range(N):
    if i == 0:  # 인덱스가 0인 경우는 1 증가 이므로
        dp[i] = 1
    else:  # 인덱스가 1이상인 경우
        max_dp = 0
        for j in range(i):  # index 이전까지의 배열 중 arr[i]보다는 작으면서 가장 큰 dp 값을 찾는다
            if max_dp < dp[j] and arr[j] < arr[i]:
                max_dp = dp[j]
        dp[i] = max_dp+1  # max_dp 값에 +1을 넣어줘야 한다
# print(dp)
print(max(dp))

참고자료 codeplus 도움받은 블로그

0%