Dynamic Programming -(최대 부분 증가 수열[LIS])

동적 계획법 중 최대 부분 증가 수열(LIS)를 구하는 문제가 있다.

 

아래 예제를 살펴보자

 

 

최대 부분 증가수열

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수  있다.

입력설명

첫째 줄은 입력되는 데이터의 수 N(1<=N<=1000, 자연수)를 의미하고,

둘째 줄은 N개의 입력데이터들이 주어진다.

출력설명

첫 번째 줄에 부분 증가수열의 최대 길이를 출력한다.

 

• 입력예제 1

8

5 3 7 8 6 2 9 4

 

• 출력 예제 1

4

 

 

이 문제는 동적계획법으로 풀어야한다.

먼저 dy라는 배열을 선언하고

dy[i]의 값은 주어진 수열 arr[i]의 값이 최대 부분 증가수열의 마지막값이 되었을 때 가능한 부분 증가수열의 갯수 중 최댓값을 뜻한다.

 

그러면 여기에서 동적계획법을 사용해야한다.

현재 5가 마지막 수열 부분이 되면 dy[1]은 1이된다.

그리고 3이 마지막 수열 부분이 되면 dy[2]는 1이 된다. 

이것을 구할 때 arr[i]와 arr[i-1]을 비교해서 만약 arr[i]>arr[i-1] 이면 dy[i-1]+dy[1]을 해주면 된다.

예를 들어보자.

지금 현재 위와 같은 그림으로 되어있다.

그럼 만약 dy[2]를 구하려고 할 때 어떻게 해야 할까?

arr[2]>arr[1]이 성사된다. 그리고 arr[2]>arr[0] 또한 성사된다.

이때 둘 중 수열의 길이가 더 큰 것과 arr[2]와 합쳐서 dy배열에 넣는다.

 

 

 

이제 코드를 작성해보자.

let arr=[5,3,7,8,6,2,9,4]
let dy=Array(arr.length).fill(0);
let answer=0;

let dy[0]=1; //어차피 무조건 1이니까 1로 초기화
for(var i=1;i<arr.length;i++){
	for(var j=i-1;j>=0;j--){
    	let max=0;
    	if(arr[i]>arr[j] && dy[j]>max){
        	max=dy[j];
        }
        dy[i]=max;
        answer=Math.max(answer,dy[i]);
    }
}
console.log(answer);