가장 긴 증가하는 부분 수열
📚 11053 - 가장 긴 증가하는 부분 수열
- dp[i]의 값을 1로 초기화
- 현재 위치보다 이전에 있는 원소의 값이 작은지 확인한다. (크거나 같으면 가장 긴 증가하는 부분 수열이 될 수 없다.)
- 작다면, 현재 위치의 이전 숫자 중, dp값에 + 1을 하여 현재 위치 dp 값과 비교한다.
- 그 중 최대값을 구한다.
예시를 보면 이와 같다.
| arr | 10 | 70 | 80 | 20 | 30 | 40 | 50 | 90 |
|---|---|---|---|---|---|---|---|---|
| dp | 1 | 2 | 3 | 2 | 3 | 4 | 5 | 6 |
n = int(input())
dp = [1] * (n + 1)
arr = list(map(int, input().split() ))
for i in range(n):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
실행 결과
Author And Source
이 문제에 관하여(가장 긴 증가하는 부분 수열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@chang626/가장-긴-증가하는-부분-수열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
