📌 [BOJ] 11053 가장 긴 증가하는 부분 수열

📖 문제

📖 예제

📖 풀이

N = int(input())
A = list(map(int, input().split()))

dp = [1] * 1001

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

print(max(dp))

본 문제의 예제에 대한 점화식은 다음 그림과 같다.
for 문을 통해 주어진 배열의 원소들을 각각 차례대로 불러온 뒤,
다시 한번 for 문을 이용하여 해당 원소의 앞에 있는 숫자들과 크기를 비교한다.
만약 크기가 더 크다면 비교한 원소가 가진 dp table의 수에 +1을 더한 값과 자신이 본래 가지고 있는 dp table의 값을 비교하여 더 큰 값으로 초기화한다.