LIS(최장증가 부분 수열)

by 모나 | TECH_ESSAY | 2025-12-21

핵심 포인트

• dp[i] 정의: i까지의 수열 중 가장 길게 증가하는 부분 (i를 포함한다)
• dp[i] = max(dp[j] + 1) (j < i && arr[j] < arr[i])
• dp 배열의 최댓값을 구하면 LIS의 길이

이런 분에게 추천: 동적계획법 및 알고리즘에 관심 있는 개발자