seq/longest_increasing_subsequence.hpp

• View this file on GitHub
• Last update: 2023-02-25 00:04:38+09:00
• Include: #include "seq/longest_increasing_subsequence.hpp"

Verified with

• test/aoj/DPL_1_D.test.cpp
• test/library_checker/math/longest_increasing_subsequence.test.cpp
• test/yukicoder/2230.test.cpp

Code

// dp[i] := 第 i 項で終わる lis 長の最大値（[1, LIS]）
template <typename T, bool strong = true>
pair<int, vc<int>> longest_increasing_subsequence(vector<T> A) {
  const int N = A.size();
  vc<T> dp(N, infty<T>);
  int lis = 0;
  vc<int> lis_rank(N);
  FOR(i, N) {
    int j = (strong ? LB(dp, A[i]) : UB(dp, A[i]));
    dp[j] = A[i];
    lis_rank[i] = j + 1;
    chmax(lis, j + 1);
  }
  return {lis, lis_rank};
}

#line 1 "seq/longest_increasing_subsequence.hpp"
// dp[i] := 第 i 項で終わる lis 長の最大値（[1, LIS]）
template <typename T, bool strong = true>
pair<int, vc<int>> longest_increasing_subsequence(vector<T> A) {
  const int N = A.size();
  vc<T> dp(N, infty<T>);
  int lis = 0;
  vc<int> lis_rank(N);
  FOR(i, N) {
    int j = (strong ? LB(dp, A[i]) : UB(dp, A[i]));
    dp[j] = A[i];
    lis_rank[i] = j + 1;
    chmax(lis, j + 1);
  }
  return {lis, lis_rank};
}

Back to top page