钱的2分法，待看：

#include<bits/stdc++.h>
using namespace std;
int n;
int cnt;
int main(){
	cin>>n;
	vector<int> dp(n+1,INT_MAX);
	int len=1;
	dp[0]=0;
	for(int i=0;i<n;i++){
		cin>>cnt;
		//					//O(log(dp.size()))
		int it=upper_bound(dp.begin(),dp.end(),cnt)-dp.begin();
		if(it>len){
			dp[++len]=cnt;
		}
		else{
			dp[it]=cnt;
		}
		for(int j=1;j<len+1;j++){
			cout<<dp[j]<<' ';
		}
		cout<<endl;
	}
	cout<<len;
	return 0;
}

二分普通方法：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> dp;        // 存储当前 LIS 的最小末尾元素
    vector<int> pos(n, -1);  // 记录 dp 中的每个位置的索引
    vector<int> prev(n, -1); // 记录每个元素的前驱索引
    for (int i = 0; i < n; i++) {
        // 使用二分查找找第一个大于等于 a[i] 的位置
        auto it = lower_bound(dp.begin(), dp.end(), a[i]);
        int idx = it - dp.begin();
        if (it == dp.end()) {
            dp.push_back(a[i]);  // 如果没有找到位置，说明 a[i] 可以作为 LIS 的新元素
        } else {
            *it = a[i];  // 替换掉 dp 中的元素
        }
        pos[idx] = i; // 记录在 dp 中每个位置对应的原始数组索引
        if (idx > 0) {
            prev[i] = pos[idx - 1]; // 记录当前元素的前驱索引
        }
    }
    // 通过前驱索引回溯构造 LIS
    vector<int> lis;
    for (int i = pos[dp.size() - 1]; i != -1; i = prev[i]) {
        lis.push_back(a[i]);
    }
    reverse(lis.begin(), lis.end());
    cout << "Max=" << dp.size() << endl;
    for (int num : lis) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

二分查找DP字典序最小：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> dp;          // 存储当前 LIS 的最小末尾元素
    vector<int> pos(n, -1);  // 记录 dp 中的每个位置的索引
    vector<int> prev(n, -1); // 记录每个元素的前驱索引
    vector<int> indices(n);  // 记录当前的元素在原数组中的位置
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(dp.begin(), dp.end(), a[i]);
        int idx = it - dp.begin();
        if (it == dp.end()) {
            dp.push_back(a[i]);
            if (!dp.empty()) {
                prev[i] = pos[idx - 1]; // 前驱索引
            }
        } else {
            *it = a[i];
            if (idx > 0) {
                prev[i] = pos[idx - 1];
            }
        }
        pos[idx] = i;
    }
    // 回溯以构造 LIS，确保字典序最小
    vector<int> lis;
    for (int i = pos[dp.size() - 1]; i != -1; i = prev[i]) {
        lis.push_back(a[i]);
    }
    reverse(lis.begin(), lis.end());
    cout << "Max=" << dp.size() << endl;
    for (int num : lis) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

从前往后代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n; 
    vector<int> a(n);         // 存储输入数组
    vector<int> dp(n, 1);     // dp[i] 存储以 a[i] 结尾的最长不下降子序列的长度
    vector<int> prev(n, -1);  // prev[i] 存储构造最长子序列时 a[i] 的前一个元素的索引
    int maxcnt = 0;           // 存储最长不下降子序列的长度
    int maxIndex = 0;         // 存储最长不下降子序列最后一个元素的索引
    for(int i = 0; i < n; i++)  cin >> a[i];
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < i; j++) {  // 这里 j 从 0 开始遍历到 i-1
            if(a[i] >= a[j] && dp[i] < dp[j] + 1) { // 更新条件：a[i] >= a[j]
                dp[i] = dp[j] + 1;
                prev[i] = j;  // 更新前驱索引
            }
        }
        if(dp[i] > maxcnt) {  // 找到当前最大长度和对应的索引
            maxcnt = dp[i];
            maxIndex = i;
        }
    }
    cout << "Max=" << maxcnt << endl;
    // 回溯构造最长不下降子序列
    vector<int> lis;
    for(int i = maxIndex; i != -1; i = prev[i]) {
        lis.push_back(a[i]);
    }
    reverse(lis.begin(), lis.end());
	int len=lis.size();
    for(int i = 0; i < len; i++) {
        cout << lis[i] << " ";
    }
    cout << endl;
    return 0;
}