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

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int,input().split()))
arrDp = [1 for i in range(N)]

for i in range(N):
    for j in range(i):
        if arr[i] > arr[j]:
            arrDp[i] = max(arrDp[i], arrDp[j]+1)

print(max(arrDp))

문제요약

증가하는 수열이 가장 긴 부분은?

설명

코드는 크게 어렵지 않을 것이다.

7
1 4 5 2 3 4 5

로 보자.

값을 하나하나 다 비교해서 수열이 가장 긴 부분에 대해서 가져가면 된다.

 

먼저 각 인덱스는 1의 수열을 가질 수 있어 1로 초기화 해주었다.

for i in range(N):
    for j in range(i):
        if arr[i] > arr[j]:
            arrDp[i] = max(arrDp[i], arrDp[j]+1)

arr를 0부터 해당 인덱스(i) 전까지 비교한다.

만약 해당 인덱스가(i) 가 비교 도중 부분 인덱스(j) 보다 크다면 Dp에 저장된 길이를 비교하는데, 자기자신이 가지고 있ㄴ는 길이, 부분 인덱스(j)에서 +1한 길이 중 더 큰 것을 저장한다.

 

print(max(arrDp))

마지막에 가장 큰 부분을 출력해주면 답을 맞출 수 있다.