[Algorithm] 최장 증가 부분 수열 (LIS)

최장 증가 부분 수열

전체 수열에서 만들 수 있는 부분 수열 중에 오름차순을 유지하며, 그 길이가 최대 길이인 부분 수열을 말한다.

(정렬된 수열의 부분 수열을 말하는 것이 아니라, 주어진 수열의 순서에서 몇 개 원소를 제거하여 오름차순을 만든 부분 수열, 그 중에 최대 길이)

최장 증가 부분 수열

최장 증가 부분 수열의 길이 구하기

최장 증가 부분 수열의 길이를 구할 때, DP(동적 프로그래밍)을 통해 구현할 수 있다.

DP 테이블을 구성하고, DP 테이블에는 각 인덱스까지 최장 증가 부분 수열의 길이를 저장한다.

 

1. DP 테이블은 각각 1로 초기화 한다.

각각 길이 1의 부분수열로 생각했을 때, 해당 인덱스에서 최장 길이는 1이다.

 

2. 부분 수열의 범위를 1씩 증가시키면서 해당 인덱스에서 최장 길이를 업데이트한다.

부분 수열이 A[0 ... K] 까지 구성하고 있을 때, A[0 ... K-1]의 원소 중에 A[K]보다 작은 값이 존재하면,

오름차순의 조건을 충족한다.

 

최장 길이의 조건을 충족하기 위해서 A[K]보다 작은 값을 가진 A[i]의 DP 테이블 값 DP[i]의 값에 +1을 한 값을 DP[K]에 저장한다. 이 때, A[i] 이전에 A[0] ~ A[i-1] 중에 더 큰 값의 DP[K] 업데이트가 있었을 수도 있기 때문에, 더 큰 값을 저장하도록 한다.

Math.max(dp[k], dp[i] + 1)

 

전체 소스 코드

for (int k = 0; k < n; k++) {
	dp[k] = 1; // dp 테이블 각각 1로 초기화
    // k 길이의 부분 수열에서 최장 길이를 구하기 위해
	for (int i = 0; i < k; i++) {
        // k 보다 앞 선 인덱스의 원소 중 k번째 원소보다 작은 값이 있다면
		if (a[i] < a[k]) {
            // dp테이블의 k번째 인덱스 업데이트
			dp[k] = max(dp[k], dp[i] + 1);
		}
	}
}

// 최장 길이 저장될 max
int max = 0;
for (int i = 0; i < n; i++) {
    max = Math.max(max, dp[i]);
}