728x90
문제
풀이
문제 요약
주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하자.
아이디어
LIS를 구하는 가장 기본적인 문제다.
점화식은 다음과 같다.
dp[i] : i번째 요소로 끝나는 LIS의 최대 길이
현재 위치 i에 대해 이전 위치 0 ~ i - 1 중 현재 위치의 값 m[i]]보다 작고, 지금까지 구한 LIS보다 dp[j] + 1이 더 긴 LIS가 된다면 다음이 성립한다.
dp[i] = max(dp[i], dp[j] + 1)
n = int(input())
m = list(map(int, input().split()))
# Please write your code here.
dp = [1] * n
for i in range(1, n):
for j in range(i):
if m[j] < m[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
풀이시간
5분
소스코드
https://github.com/rogi-rogi/problem-solving/blob/main/code-tree/Algorithm Intro/DP I/13 최대 증가 부분 수열(intro-longest-increasing-subsequence).py
728x90
'PS > Code Tree' 카테고리의 다른 글
[Code Tree] 최대 점프 횟수 [Python] (0) | 2025.07.03 |
---|---|
[Code Tree] 최대 감소 부분 수열 [Python] (0) | 2025.07.02 |
[Code Tree] 정수 사각형 최댓값의 최소 [Python] (0) | 2025.06.29 |
[Code Tree] 정수 사각형 차이의 최소 2 [Python] (0) | 2025.06.28 |
[Code Tree] 정수 사각형 최장 증가 수열 [Python] (0) | 2025.06.27 |