[알고스팟] LIS - Longest Increasing Sequence/ 최대 증가 부분 수열 (C++)

문제

algospot.com/judge/problem/read/LIS

algospot.com :: LIS

 

풀이

대표적인 DP문제 중 하나인 최대 증가 부분 수열(LIS, Longest Increasing Sequence)을 구하는 문제이다.

 

단순히 아래의 예제에서 모든 경우의 수를 찾는다고 생각해보자.

 

1 5 4 3 4 6 7

 

1번째 수, 1에서부터 재귀 함수로 LIS를 찾는다고 가정하면 1보다 큰 모든 수를 하나하나 방문할 것이다.

모든 수들에서 다시 자신보다 큰 수를 방문할 경우

5(idx: 2), 4(idx:3) ,3(idx:4)에서 자신보다 큰 6 또는 7을 방문한다.

이런 경우 같은 연산을 여러 번 반복하므로 메모이제이션을 적용하면 최적화가 가능하다.

 

dp[idx]에는 idx번째 수에서부터 시작하는 LIS의 길이를 저장한다고 하자.

 

 

0	1	2	3	4	5	6
1	5	4	3	4	6	7
						1

idx: 6인 7은 자기 자신만을 포함하는 LIS길이 1의 값을 갖는다.

 

0	1	2	3	4	5	6
1	5	4	3	4	6	7
					2	1

idx: 5 인 6은 idx+1~ idx end까지의 값 중에서 자신보다 크다면 해당 dp값 +1을 해주어 자신부터 시작하는 LIS길이를 새로 구한다. dp[idx]의 값은 dp+1의 값이 가장 큰 값으로 설정하여 최대 길이를 저장해준다.

 

다음으로 idx:1, 5인 경우를 보자.

 

0	1	2	3	4	5	6
1	5	4	3	4	6	7
	3	3	4	3	2	1

 

arr[2~6]중에서 5보다 값이 큰 경우는 6과 7이다. dp[5]+1과 dp[6]+1를 비교하면 dp[5]+1가 더 크기 때문에 dp[1] = dp[5]+1= 2 + 1 = 3의 값을

갖는다. 즉, 5(idx:1)에서 시작하는 LIS길이의 최댓값은 5 6 7의 길인 3이다.

 

최종적으로 점화식을 표현하면 아래와 같다.

dp[i] = max( dp[i] , dp[i+1 ~end] +1 ) , (arr[idx]보다 해당 값이 큰 경우에만)

 

코드