@hellotest We can recover the real LIS if we keep track of the parent of each index while we're building the dp table. This means after O(nlogn) search we just keep looping backwards using the parent array which would be O(n). The dp table would store indexes instead of values then.

int LIS(const vector<int>& v) {
int N = v.size();
vector<int> dp(N, -1);
vector<int> P(N, -1);
int dp_len = 0;
for(int i = 0; i < N; i++) {
auto it = lower_bound(dp.begin(), dp.begin() + dp_len, v[i], [](const int dp_el, const int val) {
return dp_el < val;
});
int it_index = it - dp.begin();
dp[it_index] = i;
if(it_index > 0) P[i] = dp[it_index - 1];
if(it_index == dp_len) dp_len++;
}
vector<int> lis_seq(dp_len);
int index = lis_seq.size();
for(int i = dp[dp_len - 1]; i >= 0; i = P[i]) {
lis_seq[--index] = v[i];
}
for(auto e: lis_seq) cout << e << ' '; cout << endl;
return lis_seq.size();
}