最长不下降子序列（上升同理）

最长不下降就是一条个数最多的，不下降（可以相等）的序列
比如
1 1 1 1
最长不下降子序列就是4

13，7，9，16，38，24，37，18，44，19，21，22，63，15
最长不下降子序列就是7，9，16，18，19，21，22，63

下面我们来分析一下思路

我们使用一个二维数组s[10][3],每一行的第一个代表个数，第几个，第二个代表他自身数据。第三行代表从他开始的不下降子序列的长度，第四个代表从他开始的不下降子序列的下一个元素的坐标

下面我们使用上面的例子来详细说明一下算法过程

有这样一组数据，第一行是个数，第二行是本身数据

我们采用逆序的方法，从最后一个开始

从15这个数开始的不下降子序列长度是1，下一个数据下标是0

63>15，所以63的下一行数据是1，最后一行数据是0
22<63，22下一行数据应该是2，继承63的1

21<22，继承22的2，21数据的下一行是3，最后一行是12

依此类推，就可以得到所有数据

下面是代码

#include<iostream>
using namespace std;
int main()
{
    int s[1100][20],i,j,max,n=1,l,k;
    while(cin>>s[n][1])
    {
        s[n][2]=1,s[n][3]=0;
        n++;
    }
        n--;//数字个数
        for(i=n-1;i>=1;i--)
        {
            l=0,k=0;//k是下一个数的下标,l是长度
            for(j=i+1;j<=n;j++)
            {
                if(s[i][1]<=s[j][1]&&s[j][2]>l)
                {
                    l=s[j][2];
                    k=j;
                }
            } 
            if(l>0)
            {
                s[i][2]=l+1;//最长子序列长度 
                s[i][3]=k;//下一项的下标 
            }
        }
        k=1;
        for(i=2;i<=n;i++)
        {
            if(s[i][2]>s[k][2]) k=i;
        }
        cout<<"max="<<s[k][2]<<endl;
        cout<<s[k][1];
        k=s[k][3];
        while(k!=0)
        {
            cout<<" "<<s[k][1];
            k=s[k][3];
        }
    return 0;
}

最长不上升子序列同理，小于号换成大于号就行啦