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

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

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

문제 풀이

LIS 문제 중 DP를 사용해 해결하는 가장 기초적인 문제다. 배열의 길이만큼 dp 배열을 생성해두고 i 번째 원소에 대해 최대 증가 수열의 값을 도출하면 dp의 max값이 정답이 된다.

• 초기값은 1로 설정
• i 번째는 i - 1 좌표까지의 원소들 중 자신보다 작으며 그 중 최대인 값 + 1이 된다.
• i번째 값이 산출되면 기존 최댓값과 비교, 갱신
• 순회가 모두 끝나고 최댓값 출력

python 코드

import sys

input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))
max_v = 1
dp = []
for i in range(N):
    b = 0
    for j in range(i):
        if nums[i] > nums[j]:
            b = max(b, dp[j])
    dp.append(b + 1)
    max_v = max(max_v, dp[i])
print(max_v)