#include <iostream>
#include <vector>
#include <algorithm>
std::size_t LIS_length(const std::vector<int> &s)
{
std::vector<int> dp; // dp[i]是长度为i+1的最长递增子序列的最后一个值
for (auto x: s)
{
auto it = std::upper_bound(dp.begin(), dp.end(), x);
if (it == dp.end())
dp.push_back(x);
else
*it = x;
}
return dp.size();
}
std::vector<int> LIS_nlogn(const std::vector<int> &s)
{
std::vector<int> dp; // dp[i]是长度为i+1的最长递增子序列的最后一个值
std::vector<std::size_t> dpIdx; // dp[i]在原序列里的索引
std::vector<std::size_t> prev; // 当前元素可构造LIS的上一个索引
std::size_t earliest = -1; // 用于输出最早的LIS
for (std::size_t i = 0; i < s.size(); i++)
{
auto x = s[i];
auto it = std::upper_bound(dp.begin(), dp.end(), x); // 二分查找，O(logn)
if (it == dp.end()) // s[i] > s[0..i-1]
{
dp.push_back(x);
if (dpIdx.size() == 0)
prev.push_back(-1); // 这是指无符号最大值
else
prev.push_back(dpIdx.back()); // 获取上一个元素的索引
dpIdx.push_back(i); // 当前元素的索引
earliest = i;
}
else
{
auto index = std::distance(dp.begin(), it); // dp[index]是最小的大于s[i]的元素
// 更新dp[index]使得长度为index+1的LIS的最后一个元素尽可能的小，以便后续可以获得更长的LIS。
// 这个被覆盖的元素已经被用来构造过LIS，后续可以用当前元素来构造LIS。这是贪心策略
dp[index] = x;
dpIdx[index] = i;
if (index == 0)
prev.push_back(-1);
else
prev.push_back(dpIdx[index - 1]);
}
}
std::vector<int> res;
for (std::size_t i = earliest; i < s.size(); i = prev[i])
res.push_back(s[i]);
std::reverse(res.begin(), res.end());
return res;
}
