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

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

별로 특별할 것 없이 lower_bound를 사용해서 풀어주면 LIS의 길이까지는 무리 없이 구해줄 수 있다.

여기서 실제 LIS를 재구성해내는데 조금 어려움을 겪었는데, 결과적으로는 아래의 방법을 사용하였다.

LIS를 풀면서 아래의 정보를 유지해준다.

• P[i]: A[i]가 LIS의 몇 번째 수로서 포함될 수 있었는가?

LIS의 길이를 구한 뒤에 P[i]를 뒤에서부터 보면서 답을 재구성해주면 된다.

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

using namespace std;

const int kMaxN = 1000000;

int N;
int A[kMaxN];
int P[kMaxN];

vector<int> CACHE;
vector<int> LIS;

int main(void)
{
  // Read input
  scanf(" %d", &N);
  for (int i = 0; i < N; ++i)
  {
    scanf(" %d", &A[i]);
  }

  // Get length
  for (int i = 0; i < N; ++i)
  {
    auto it = lower_bound(CACHE.begin(), CACHE.end(), A[i]);
    if (it == CACHE.end())
    {
      CACHE.emplace_back(A[i]);
      P[i] = (int)CACHE.size() - 1;
    }
    else
    {
      *it = A[i];
      P[i] = (int)(it - CACHE.begin());
    }
  }

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

  int target = (int)CACHE.size() - 1;
  for (int i = N - 1; i >= 0 && target >= 0; --i)
  {
    if (P[i] == target)
    {
      LIS.emplace_back(A[i]);
      --target;
    }
  }

  for (auto r = LIS.rbegin(); r != LIS.rend(); ++r)
  {
    printf("%d ", *r);
  }
  printf("\n");

  return 0;
}