对于以i为结尾的最长不下降子序列的长度f[i]，可以如下考虑：

• j从1循环到i-1，若a[j]<=a[i]，则可以把a[i]接到以j为结尾的最长不下降子序列当中，则有f[i] = f[j]+1，这就是状态转移方程
• 最后对f求一个最大值就是问题①的答案

但这题要求求出最长不下降子序列，我们可以用一个pre[i]表示以i为结尾的最长不下降子序列的前一个元素（前驱），每次转移时顺便执行pre[i] = j，然后从最长不下降子序列的末尾开始遍历再逆序就是答案

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int a[N],f[N],pre[N];
int n=1,x,maxn,k;

int main()
{
    while(cin >> x)
    {
        a[n] = x;
        f[n++] = 1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[j]<=a[i] && f[i]<f[j]+1)
            {
                f[i] = f[j]+1;
                pre[i] = j; //转移的时候更新一下前驱
                if(f[i]>maxn)
                {
                    maxn = f[i];
                    k = i; //遍历起点
                }
            }
        }
    }
    cout << "max=" << maxn << endl;
    vector<int> ans;
    while(k!=0)//类似链表遍历
    {
        ans.push_back(a[k]);
        k = pre[k];
    }
    for(int i=ans.size()-1;i>=0;i--)
        cout << ans[i] << " ";
    return 0;
}