백준 #11053 가장 긴 증가하는 부분 수열

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline


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

for i in range(n):
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

풀이

dp문제를 풀어본 사람이라면 한번쯤은 풀어보았을 문제이다.

dp[i]는 i번째 수를 마지막 원소로 가지는 부분 수열의 최대 길이이다.

점화식으로 쓰면 다음과 같다.

\[모든 \ 0 \le j \lt i 에 \ 대하여, \ D[i]=max(D[i], D[j]+1) \ (if \ array[j] \lt array[i])\]

이중 for문을 써주면서 바깥쪽 for문은 전체 길이만큼돌고 안쪽 for문은 해당 index까지만 돌아주면서 dp 값을 갱신해주면된다!