Longest Increasing Subsequences

가장 긴 증가하는 부분 수열

 

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

11053번: 가장 긴 증가하는 부분 수열

 

Memoization 할 Array D 

D[n] 은 Arr[1] ~ Arr[n] 까지 있을 때, Arr[n]을 마지막으로 하는 LIS 의 길이

D[n] 에 A[n]은 항상 포함되어야 한다. 

 

예제에서 6개의 숫자

 10 20 10 30 20 50 의 가장 긴 부분수열의 길이는 4이다. 

 10 - 20 - 30 - 50 

 

for (int i=0; i<n; i++) {
	d[i] = 1;
	for (int j=0; j<i; j++) {
		if (arr[j] < arr[i] && d[i] < d[j]+1) {
			d[i] = d[j]+1;
		}
	}
}