가장 긴 증가하는 부분 수열 2

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

사람마다 푸는 방법은 여러가지가 있을텐데, 나는 그중에 가장 무지성으로 풀 수 있는(물론 복잡도는 다른 알고리즘에 뒤지지 않는다) lower_bound 풀이를 사용했다.

이 풀이는 배열을 처음부터 끝 원소까지 순차적으로 훑어가면서 아래의 벡터(배열이 아니다, 동적으로 변하는 벡터다)를 유지한다.

• CACHE[len]: 길이가 len인 LIS중 끝 원소가 가장 작은 LIS의 끝 원소

저 배열을 유지하는 방법은 아래와 같다.

i번째 원소를 보고 있다고 하자.

CACHE에서 A[i]의 lower_bound를 찾았고, 이 원소, lb,가 존재했다고 하자(즉, end를 리턴하지 않음).

그 이야기인 즉슨 lb를 A[i]로 바꿔치기 해도 여전히 lb로 끝났던 LIS만큼은 그대로 만들 수 있다는 이야기이다.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<int> CACHE;

int main(void)
{
  scanf(" %d", &N);
  for (int it = 0; it < N; ++it)
  {
    int number;
    scanf(" %d", &number);

    auto l = lower_bound(CACHE.begin(), CACHE.end(), number);
    if (l == CACHE.end())
    {
      CACHE.emplace_back(number);
    }
    else
    {
      *l = number;
    }
  }

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

  return 0;
}