#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N], b[N], c[N], n;
// a数组保存整数序列
// b数组用来逆序考虑，b[i]为起点可以构成的最大不降序列
// c数组是保存构成不降序列a[i]的下一个数的下标
int main() {
	cin >> n;//输入
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = 1;//初始以a[i]为起点的数字默认最大不降序列
	}//输入
	for (int i = n - 1; i >= 1; i--) {
		int max_len = 0, weizhi = 0;
		//max_len最长长度，位置。
		for (int j = i + 1; j <= n; j++) {
			if (a[i] <= a[j] && b[j] > max_len) {//打擂台
				max_len = b[j];//更新
				weizhi = j;
			}
		}
		if (max_len > 0) {//如果找到可以连接的最长不降序列，就更改a[i]的b[i]和c[i]
			b[i] = max_len + 1;
			c[i] = weizhi;
		}
	}
	int max_l = 1, k = 1;
	for (int i = 1; i <= n; i++) {
		if (b[i] > max_l) {//max_l是最长的，擂台法
			max_l = b[i];
			k = i;
		}
	}
	cout << "max=" << max_l << endl;//输出
	while (k != 0) {
		cout << a[k] << " ";//输出
		k = c[k];//把k放到大哥的位置
	}
	return 0;
}

#include<bits/stdc++.h>//头文件 
using namespace std;//命名空间 
const int N=1e6+10;//N 
int a[N],b[N],c[N],n;//定义数组变量 
// a数组保存整数序列
// b数组用来逆序考虑，b[i]为起点可以构成的最大不降序列
// c数组是保存构成不降序列a[i]的下一个数的下标
int main(){ 
	cin>>n;//输入 
	for(int i=1;i<=n;i++){
		cin>>a[i];//输入 
		b[i]=1;//初始以a[i]为起点的数字默认最大不降序列 
	}
	for(int i=n-1;i>=1;i--){//把数字序列中，倒数第二个n-1，倒数第三个n-2...第一个 
		int max_len=0,weizhi=0;
	//max_len是记录a[i]后面比我大的数，以它为起点最长不降序列长度最大的
	//weizhi是记录a[i]和谁构成的最长不降序列 
		for(int j=i+1;j<=n;j++){ 
			if(a[i]<=a[j]&&b[j]>max_len){
				max_len=b[j];//打擂台 
				weizhi=j;//更新状态
			}
		}
		if(max_len>0){
			b[i]=max_len+1;
			c[i]=weizhi;
		}
	}
	int max_l=1,k=1;//定义变量 
	for(int i=1;i<=n;i++){
		if(b[i]>max_l){
			max_l=b[i];
			k=i;
		}
	}
	cout<<"max="<<max_l<<endl;//输出结果 
	while(k!=0){
		cout<<a[k]<<" ";//输出 
		k=c[k];
	}
	return 0;//结束 
}

1259：【例9.3】求最长不下降序列

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
int a[N],b[N],c[N],n;
// a数组保存整数序列
// b数组用来逆序考虑，b[i]为起点可以构成的最大不降序列
// c数组是保存构成不降序列a[i]的下一个数的下标
int main(){
    cin>>n;//输入
    for(int i=1;i<=n;i++){
        cin>>a[i];//输入
        b[i]=1;//初始以a[i]为起点的数字默认最大不降序列
    }
    for(int i=n-1;i>=1;i--){
    //把数字序列中，倒数第二个n-1，倒数第三个n-2....第一个1
        int max_len=0,weizhi=0;
    //max_len是记录a[i]后面比我大的数，以它为起点最长不降序列长度最大的
    //weizhi是记录a[i]和谁构成的最长不降序列
        for(int j=i+1;j<=n;j++){//擂台法进行比较
            if(a[i]<=a[j]&&b[j]>max_len){
                max_len=b[j];
                weizhi=j;
            }
        }
        if(max_len>0){//如果找到可以连接的最长不降序列，就更改a[i]的b[i]和c[i]
            b[i]=max_len+1;
            c[i]=weizhi;
        }
    }
    int max_l =1,k=1;//max_l是记录最长长度的擂台，k记录起点的位置
    for(int i=1;i<=n;i++){//擂台法求最长的长度和最长起点的位置
        if(b[i]>max_l){
            max_l=b[i];
            k=i;
        }
    }
    cout<<"max="<<max_l<<endl;//打印长度
    while(k!=0){//从起点开始根据c[i]记录的位置打印出最长序列
        cout<<a[k]<<" ";
        k=c[k];
    }
    return 0;
}

#include<bits/stdc++.h>//头文件
using namespace std;//命名空间
const int N = 1e3 + 10; //建1个变量N大小是10010
int a[N], b[N], c[N], n; // a数组保存整数序列 b数组用来逆序考虑，b[i]为起点可以构成的最大不降序列 c数组是保存构成不降序列a[i]的下一个数的下标
int main() {
	cin >> n; //输入
	for (int i = 1; i <= n; i++) {
		cin >> a[i]; //输入
		b[i] = 1; //将每个数字设为1
	}
	for (int i = n - 1; i >= 1; i--) {
		int max_len = 0, weizhi = 0; //建2个变量max_len和weizhi
		for (int j = i + 1; j <= n; j++) {
			if (a[i] <= a[j] && b[j] > max_len) {//判断
				max_len = b[j];//打擂台 赢了就更新
				weizhi = j;//更新状态
			}
		}
		if (max_len > 0) {//判断
			b[i] = max_len + 1;//
			c[i] = weizhi;
		}
	}
	int max_l = 1, k = 1;//建2个变量
	for (int i = 1; i <= n; i++) {
		if (b[i] > max_l) {//判断
			max_l = b[i];//打擂台 赢了就更新
			k = i;//更新状态
		}
	}
	cout << "max=" << max_l << endl;//输出
	while (k != 0) {
		cout << a[k] << " ";//输出
		k = c[k];//k到他大哥的位置
	}
	return 0;//结束
}

using namespace std;//命名空间 
const int N =1e6+10;//建个变量N
int a[N],b[N],c[N],n;//定义数组变量 
// a数组保存整数序列
// b数组用来逆序考虑，b[i]为起点可以构成的最大不降序列
// c数组是保存构成不降序列a[i]的下一个数的下标
int main(){
	cin>>n;//输入 
	for(int i=1;i<=n;i++){
		cin>>a[i];//输入 
		b[i]=1;
	}
	for(int i=n-1;i>=1;i--){
		int max_len=0,weizhi=0;//定义变量 
		for(int j=i+1;j<=n;j++){
			if(a[i]<=a[j]&&b[j]>max_len){//判断
				max_len=b[j];
				weizhi=j;
			}
		}
		if(max_len>0){//判断
			b[i]=max_len+1;
			c[i]=weizhi;
		}
		
	}
	int max_l =1,k=1;//定义变量 
	for(int i=1;i<=n;i++){
		if(b[i]>max_l){//判断
			max_l=b[i];
			k=i;
		}
	}
	cout<<"max="<<max_l<<endl;
	while(k!=0){
		cout<<a[k]<<" ";//输出 
		k=c[k];
	}
    return 0;//结束 
}