1. 最长不上升子序列的长度
2. 这样的序列有多少个（或者 最长上升子序列）

#include <iostream>

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N],g[N]; // g[]:记录每个序列的最后一个元素

int main()
{
    while(cin >> a[n]) n ++ ; // 下标从0开始

    for(int i =0;i<n;i++)
    {
        f[i] = 1;
        for(int j=0;j<i;j++)
            if(a[i] <= a[j]) f[i] = max(f[i],f[j] + 1);
    }

    int res=0;
    for(int i=0;i<n;i++) res=max(res,f[i]);
    cout<<res<<endl;

    int cnt=0; // 表示当前序列有多少个，第一个序列的下标是0,g[0]=..
    for(int i=0;i<n;i++)
    {
        int k = 0;  // k:枚举哪个序列
        while(k < cnt && g[k] < a[i]) k ++;
        g[k] = a[i];
        if(k >= cnt) cnt ++ ;
    }

    cout<<cnt<<endl;

    return 0;
}

最长上升子序列优化就是贪心 + 二分 + 单调栈

详情见我这里

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N];
// 模拟堆栈
vector<int> down; // 最长下降子序列(包含相等)，从后往前看就是最长上升子序列(包含相等)
vector<int> up;   // 最长上升子序列(不包含相等)

int main()
{
    while(cin >> a[n]) n++;

    for(int i=n-1;i>=0;i--)
    {
        if(down.empty() || a[i] >= down.back()) down.push_back(a[i]);
        else
        {
            *upper_bound(down.begin(),down.end(),a[i])  = a[i];
        }
    }
    cout<<down.size()<<endl;

    for(int i=0;i<n;i++)
    {
        if(up.empty() || a[i] > up.back()) up.push_back(a[i]);
        else
        {
            *lower_bound(up.begin(),up.end(),a[i]) = a[i];
        }
    }
    cout<<up.size()<<endl;

    return 0;
}