最长严格/非严格递增子序列 (LIS)

最长严格/非严格递增子序列 (LIS)

一维

注意子序列是不连续的。使用二分搜索，以 \(\mathcal O(N\log N)\) 复杂度通过，另也有 \(\mathcal O(N^2)\) 的 \(\tt dp\) 解法。\(\sf dis\) \(\rm dis\)

vector<int> val; // 堆数
for (int i = 1, x; i <= n; i++) {cin >> x;int it = upper_bound(val.begin(), val.end(), x) - val.begin(); // low/upp: 严格/非严格递增if (it >= val.size()) { // 新增一堆val.push_back(x);} else { // 更新对应位置元素val[it] = x;}
}
cout << val.size() << endl;

二维+输出方案

vector<array<int, 3>> in(n + 1);
for (int i = 1; i <= n; i++) {cin >> in[i][0] >> in[i][1];in[i][2] = i;
}
sort(in.begin() + 1, in.end(), [&](auto x, auto y) {if (x[0] != y[0]) return x[0] < y[0];return x[1] > y[1];
});vector<int> val{0}, idx{0}, pre(n + 1);
for (int i = 1; i <= n; i++) {auto [x, y, z] = in[i];int it = lower_bound(val.begin(), val.end(), y) - val.begin(); // low/upp: 严格/非严格递增if (it >= val.size()) { // 新增一堆pre[z] = idx.back();val.push_back(y);idx.push_back(z);} else { // 更新对应位置元素pre[z] = idx[it - 1];val[it] = y;idx[it] = z;}
}vector<int> ans;
for (int i = idx.back(); i != 0; i = pre[i]) {ans.push_back(i);
}
reverse(ans.begin(), ans.end());
cout << ans.size() << "\n";
for (auto it : ans) {cout << it << " ";
}