최장증가수열(LIS)

최장증가수열(LIS : Longest Incresing Subsequence)

---

수열이 나열되어있을 때, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 문제

ex)

3,2,6,4,5,1 라는 수열에서 최장증가 수열은 [2,4,5] 혹은 [3,4,5]이고, 길이는 3이다

 

 

이는 어떻게 구할까?

 

• 부분집합

부분집합을 통해 증가하면서 길이가 가장 긴 수열을 구할 수도 있지만,

부분집합은 시간복잡도가 2의 n승이기 때문에 수열이 길어질수록 시간적으로 부담이된다.

https://java-is-happy-things.tistory.com/8?category=1266501 

[Java] 부분집합

 

• DP

LIS[i] : i원소가 수열의 마지막일 때 최장의 값

이 정의를 토대로 DP를 이용하여 풀어본다.

LIS[i]의 최소값은 자기 자신만 부분수열을 구성하는 것이므로 1이다. 

모든 값은 처음 1로 초기화를 해주고, 자신의 앞 원소까지 비교하여 자신이 포함할 수 있는 수 중 가장 큰값을 더하면 길이를 구할 수 있다.

 

- O(n^2)

- [3,2,6,4,5,1]

LIS[1]	LIS[2]	LIS[3]	LIS[4]	LIS[5]	LIS[6]
1	1	{3,6} = 2	{3,4} = 2	{3,4,5} = 3	1

LIS[2] : 2번째 원소인 2를 마지막으로 했을 때, 자신 이전값까지 포함할 수 있는 값(자신보다 작은값)이 없으므로 1

LIS[3] : 3번째 원소인 6을 마지막으로 했을 때, 앞 원소 3과 2를 포함할 수 있고, 길이가 같으므로 둘 중 하나 선택 후 +1

LIS[5] : 5번째 원소인 5를 마지막으로 했을 때, 포함할 수 있는 원소 중 가장 큰 LIS[4] 선택하여 +1

 

[입력]

6
3 2 6 4 5 1

 

[출력]

3

 

[코드구현]

public class DP1_LISTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner (System.in);
		int N = sc.nextInt();		//수열의 크기
		int [] arr = new int[N];		//수열의 원소들 저장
		int [] LIS = new int[N];		// 자신을 끝으로 하는 LIS길이
		
		for(int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		int max=0; 
		for(int i=0; i<N; i++) {		//모든원소에 대해 
			LIS[i]=1;	//자기혼자 LIS 구성할때의 길이 1로 초기화
			for(int j=0; j<i; j++) {	//첫원소부터 i원소 직전까지만 비교
				if(arr[j]<arr[i] && LIS[i]<LIS[j]+1) {  //arr[j]<arr[i] 증가 모습
					LIS[i]=LIS[j]+1;
				}
			}
			if(max<LIS[i]) max=LIS[i];
		}
		System.out.println(max);
		sc.close();
	}

}