LIS

LIS: Longest Increasing Subsequence
최장 증가 부분 수열

원소가 n개인 수열에서 최대한 많은 원소를 골라 증가하는 부분 수열을 만드는 문제이다.

예를 들어 {10,20,10,30,20,50} 과 같은 수열이 있을 때 {30,50}, {10,30,50}, {10,20,30,50} 과 같이 증가하는 부분 수열을 만들 수 있다.
이중 {10,20,30,50}이 가장 긴 부분 수열이다.

DP를 이용하여 해결할 수 있다.

• (N²)
  DP 테이블을 만들어 해결할 수 있다.
  수열의 크기가 n이라고 했을 때 크기가 n인 DP 배열을 만든다.

public static int lis(int n, int[] arr)
{
	int[] dp = new int[n]; // 수열과 같은 크기의 dp 테이블
	Arrays.fill(dp, 1); // 자기자신만으로 길이 1의 증가 수열이므로 1로 초기화
	for (int i=1; i<n; i++)
	{
		for (int j=0; j<i; j++)
		{
			if (arr[j] < arr[i]) // 앞쪽에 자기보다 작은 수가 있다면
				// 해당 원소 길이+1과 최댓값을 비교한다
				dp[i] = Math.max(dp[i], dp[j] + 1); 
		}
	}
	
	int max = dp[0];
	for (int i=0; i<n; i++)
	{
		System.out.println(dp[i]);
	}
	
	for (int i=1; i<n; i++)
	{
		if (dp[i] > max)
			max = dp[i];
	}
	return max; // dp 테이블에서 최대값을 반환한다
}

• O(NlogN)
  앞의 방법에서는 각 원소 위치 조사할 때 마다 앞의 모든 원소 탐색했다.
  이때 탐색과정에서 O(N²)의 시간 복잡도를 가졌다.

앞의 모든 원소 탐색하는 과정을 이진 탐색을 사용하여 O(NlogN)으로 줄여보자.

1. 현재 위치에서 부분 수열의 길이가 추가될 가능성이 있는가?
   => 앞에서는 앞의 모든 원소의 크기와 비교하면서 파악했다.
   그 대신

2. 현재까지 조사한