[JAVA] 최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)
2023. 8. 20. 16:25
JAVA/알고리즘 개념 정리
LIS 란? Longest Increasing Subsequence ex) 수열 A = {10, 20, 10, 30, 20, 50}가 주어지고 가장 긴 증가하는 부분 수열을 구하는 문제 증가하는 부분 수열을 모두 구해보면 아래와 같음 {10}, {20}, {30}, {50} {10, 20}, {10, 30}, {20, 30}, {20, 50}, {30, 50} {10, 20, 30}, {10, 20, 50}, {10, 30, 50}, {20, 30, 50} {10, 20, 30, 50} 이 중 가장 길이가 긴 부분 수열은 {10, 20, 30, 50} 해결 방법 1 - O(n^2) 가장 쉬운 해결 방법은 일반적인 dp를 사용하는 방법 dp[i] = dp[i - 1]과 arr[i]를 포함시켜 만들 수 있는..