1. 直接求最长不上升子序列
2. 第二问
   从前往后扫描每个数，对于每个数：
   情况1：如果现有的子序列的结果都小于当前数， 则创建新子序列
   情况2: 将当前数放到结尾大于等于它的最小的子序列后面
   g[]: 从小到大摆放子序列的结尾元素，子序列是最长不上升子序列

#include<iostream>

using namespace std;
const int N = 1010;
int a[N], f[N], g[N];
int n;

int main() {

    while (cin >> a[n]) n++;
    int res = 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);
            }
            res = max(res, f[i]);
        }
    }

    cout << res << endl;
    //贪心流程：
    //从前往后扫描每个数，对于每个数：
    //情况1：如果现有的子序列的结果都小于当前数， 则创建新子序列；
    //情况2: 将当前数放到结尾大于等于它的最小的子序列后面；
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int k = 0;
        //c< a[i], c 是在g数组中的， 小于a[i]的最大值
        while (k < cnt && g[k] < a[i]) k++;
        g[k] = a[i];
        if (k >= cnt) cnt++;
    }

    cout << cnt << endl;
}