[실버2] 11053번 : 가장 긴 증가하는 부분 수열

Quesuemon·2021년 4월 11일
0

코딩테스트 준비

목록 보기
81/111

🛠 문제

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


👩🏻‍💻 해결 방법

dp[i]는 arr[i]를 마지막 원소로 가지는 부분 수열의 최대 길이라고 정의하면,
0 <= j < i에 대하여, dp[i] = max(dp[i], dp[j] + 1) if arr[j] < arr[i] 라는 점화식을 만들 수 있다

소스 코드

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

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

print(max(dp))

0개의 댓글