본문으로 바로가기

모든 입력값을 음수로 받아 LIS를 구하면 LDS를 구할 수 있다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> v;

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

  int x;
  while (n--) {
    scanf("%d", &x);
    x = -x;

    if (v.empty() || v.back() < x) {
      v.push_back(x);
    } else {
      auto it = lower_bound(v.begin(), v.end(), x);
      *it = x;
    }
  }

  printf("%d\n", (int)v.size());
  return 0;
}

댓글을 달아 주세요