[DP] LIS(Longest Increasing Subsequence) 최장 증가 부분 수열

[3, 5, 1, 9, 2, 1, 4, 8] 과 같은 수열에서 임의의 수를 제거해 정렬된 상태인 부분 수열을 구하는데 길이가 최대가 되는 부분 수열을 찾는 문제가 최장 증가 부분 수열 문제이다.

알고리즘을 정리하자면 아래와 같다.

• 현재 원소를 dp배열의 정렬이 되도록 덮어씌운다.(삽입X)

예를들어 dp 배열에 [1,4,8]이 있다면 3을 어디에 덮어씌워야 정렬이 유지가 되는가이다. 4를 3으로 대체한다면 [1,3,8]이 되어 정렬을 유지할 수 있다.

• dp 배열의 길이가 최장 증가 부분 수열의 길이이다.

아래 알고리즘 동작 방식을 보면 쉽게 이해할 수 있다.

dp배열의 크기는 1이였고 3은 들어갈 공간이 하나 밖에 없으니 그대로 삽입한다.

dp 배열은 [3][ ] 이였고 5는 마지막 원소가 되어야 한다.

dp 배열은 [3][5][ ] 이였고, 1은 맨 처음 원소가 되어야 한다.
맨 뒤에 들어가는 경우가 아니면 dp 배열의 길이는 늘어나지 않는다.

dp 배열은 [1][5][ ] 이였고, 9는 마지막 원소가 되어야 한다.

dp 배열은 [1][5][9][ ] 이였고 2는 5의 자리를 대체하면 된다.

dp 배열은 [1][2][9][ ] 이였고 1은 맨 앞으로 가면 된다.

dp 배열은 [1][2][9][ ] 이였고 4는 9의 자리를 대체한다.

dp 배열은 [1][2][4][ ] 이였고 8은 마지막 자리로 가면 된다.

최장 증가 부분 수열은 길이가 4이다.

int LIS(vector<int> S) {
	vector<int> dp(S.size(), INT_MIN);
	int max_idx = 0;
	for (int i = 0; i < S.size(); i++) {
		int idx = upper_bound(S.begin(), S.begin() + max_idx, S[i]) - S.begin();
		if (idx == max_idx)max_idx++;
		dp[idx] = S[i];
	}
	return max_idx;
}

코드에서 upper_bound를 사용한게 중요하다. lower_bound를 쓰게 되면 중복된 숫자가 들어올 때를 처리할 수 없다.