longest_increasing_subsequence.hpp¶

SECTIONDP INCLUDEnoya/longest_increasing_subsequence.hpp

求一个最长严格上升子序列，并返回所选元素的原下标。

Complexity: Time: O(n log n). Space: O(n).

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n log n).
/// Space: O(n).

#include <algorithm>
#include <vector>

namespace noya {

/// @brief Compute indices of a longest strictly increasing subsequence.
/// @return Indices into A forming a longest increasing subsequence.
template <class T>
std::vector<int> longest_increasing_subsequence(const std::vector<T> &A) {
  if (A.empty())
    return {};
  std::vector<T> B;
  std::vector<int> idx;
  int N = int(A.size());
  std::vector<int> pre(N, -1);
  for (int i = 0; i < N; i++) {
    T a = A[i];
    int j = std::lower_bound(B.begin(), B.end(), a) - B.begin();
    if (j == int(B.size())) {
      idx.push_back(i);
      B.push_back(a);
    } else {
      idx[j] = i;
      B[j] = a;
    }
    if (j > 0) {
      pre[i] = idx[j - 1];
    }
  }
  std::vector<int> ans;
  for (int cur = idx.back(); cur != -1; cur = pre[cur])
    ans.push_back(cur);

  std::reverse(ans.begin(), ans.end());
  return ans;
}

} // namespace noya

#ifndef NOYA_LONGEST_INCREASING_SUBSEQUENCE_HPP
#define NOYA_LONGEST_INCREASING_SUBSEQUENCE_HPP 1

/// @complexity Time: O(n log n).
/// Space: O(n).

#include <algorithm>
#include <vector>

namespace noya {

/// @brief Compute indices of a longest strictly increasing subsequence.
/// @return Indices into A forming a longest increasing subsequence.
template <class T>
std::vector<int> longest_increasing_subsequence(const std::vector<T> &A) {
  if (A.empty())
    return {};
  std::vector<T> B;
  std::vector<int> idx;
  int N = int(A.size());
  std::vector<int> pre(N, -1);
  for (int i = 0; i < N; i++) {
    T a = A[i];
    int j = std::lower_bound(B.begin(), B.end(), a) - B.begin();
    if (j == int(B.size())) {
      idx.push_back(i);
      B.push_back(a);
    } else {
      idx[j] = i;
      B[j] = a;
    }
    if (j > 0) {
      pre[i] = idx[j - 1];
    }
  }
  std::vector<int> ans;
  for (int cur = idx.back(); cur != -1; cur = pre[cur])
    ans.push_back(cur);

  std::reverse(ans.begin(), ans.end());
  return ans;
}

} // namespace noya

#endif // NOYA_LONGEST_INCREASING_SUBSEQUENCE_HPP

#include <algorithm>
#include <vector>

/// @complexity Time: O(n log n).
/// Space: O(n).

namespace noya {

/// @brief Compute indices of a longest strictly increasing subsequence.
/// @return Indices into A forming a longest increasing subsequence.
template <class T>
std::vector<int> longest_increasing_subsequence(const std::vector<T> &A) {
  if (A.empty())
    return {};
  std::vector<T> B;
  std::vector<int> idx;
  int N = int(A.size());
  std::vector<int> pre(N, -1);
  for (int i = 0; i < N; i++) {
    T a = A[i];
    int j = std::lower_bound(B.begin(), B.end(), a) - B.begin();
    if (j == int(B.size())) {
      idx.push_back(i);
      B.push_back(a);
    } else {
      idx[j] = i;
      B[j] = a;
    }
    if (j > 0) {
      pre[i] = idx[j - 1];
    }
  }
  std::vector<int> ans;
  for (int cur = idx.back(); cur != -1; cur = pre[cur])
    ans.push_back(cur);

  std::reverse(ans.begin(), ans.end());
  return ans;
}

} // namespace noya