https://www.acmicpc.net/problem/11053

https://st-lab.tistory.com/137

한 수열에서 가장 긴 증가하는 부부 수열의 길이를 구하는 문제이다.

가장 작은 입력값을 시작으로 원하고자 하는 입력값의 해를 구할 수 있는 동적 프로그래밍으로 풀 수 있다.

예시를 중심으로 문제를 정리해보겠다.

가장 긴 증가하는 부분수열을 LIS 라고하자.

즉, 구하는 답은 LIS의 길이를 구하는 것이다.

seq을 수열을 저장하는 배열이라고 하자. dp를 각 수열을 포함하는 LIS 길이를 저장하는 배열이라고 하자.

예를 들면 이러하다.

seq = [10] 일 때,
dp = [1] 이다. 
		10이 마지막일 때 10을 마지막으로 하는 수열의 LIS 가 10이다. 

seq = [10,20] 일 때,
	dp = [1, 2] 이다. 
	20이 마지막 요소일 때, 20을 마지막으로 하는 수열의 LIS가 10,20이다.

seq = [10,20,10]일 때,
	dp = [1, 2, 1]이다.
	10이 마지막 요소일 때, 10을 마지막으로 하는 수열의 LIS 는 10이다. 

seq = [10,20,10,30]일 때,
	dp = [1, 2, 1, 3]이다.
	30이 마지막 요소일 때, 30을 마지막으로 하는 수열의 LIS 10,20,30이다.

seq  = [10,20,10,30,20,50] 일때  
LIS는 10,20,30,50이다. 

왜 각 요소가 마지막일때 LIS 길이를 dp에 저장해야 하나?

각 요소까지의 LIS 길이를 저장하면 안되나?

seq  = [10,20,10,30,20,50] 일때  
LIS는 10,20,30,50이다
만약 각 요소까지의 LIS 길이를 dp에 저장한다고 한다면, 
seq  = [10,20,10,30,20,50]
dp =   [1, 2, 2, 3, 3, 4]
가 된다. 답은 맞다. 

다른 예시로,
seq  = [10,20,10,30,20,50,11,12,13,14] 일 떄,
LIS는 10,11,12,13,14 이다.
만약 각 요소까지의 LIS 길이를 dp에 저장한다고 한다면, 
seq  = [10,20,10,30,20,50,11,12,13,14] 
dp =   [1, 2, 2, 3, 3, 4, 5, 6, 7, 8]
틀린 답이 나온다.

LIS는 뒤에 오는 요소에 따라 바뀔 수 있다.
 
그러므로 각 요소가 마지막 요소일 때, LIS길이를 dp에 저장해둬야 한다. 

seq  = [10,20,10,30,20,50]
dp =   [1, 2, 1, 3, 2, 4]