[그리디 알고리즘] 가장 긴 증가하는 부분 수열 2

예제 입력 1

6

10 20 10 30 20 50

예제 출력 1

4

 

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

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

- N제한이 너무 크기 때문에, 다이나믹 알고리즘으로는 풀 수 없다.

- 따라서, 1차원 배열을 이용해 lower_bound()로 현재 A 원소와 같거나 더 큰 D 원소를 찾아, 존재하면 덮어쓰고 없으면 추가해주는 방식으로 "길이만" 정확하게 구할 수 있다.

#include <stdio.h>
#include <vector>
#include <algorithm>

const int MAX_COUNT = 1000000;

using namespace std;

int N;
int numbers[MAX_COUNT];

int main(void)
{
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &numbers[i]);
	}

	vector<int> D;

	for (int i = 0; i < N; i++)
	{
		auto it = lower_bound(D.begin(), D.end(), numbers[i]);

		if (it == D.end())
		{
			D.push_back(numbers[i]);
		}
		else
		{
			*it = numbers[i];
		}
	}

	printf("%d\n", D.size());

	return 0;
}