本题使用动态规划，用dp数组去保存当前数的最长不上升序列长度。那么后面的下一个数的最长不上升序列长度就是前面大于等于这个数的长度中最大的那一个加一。

至于第二问：根据dilworth定理我们知道可划分的最少不上升子序列的数目就是其最长下降子序列的长度。所以求其上升的最长序列即可。
这是O（n^2）复杂度的解法。 
#include <bits/stdc++.h>


using namespace std;
const int maxn = 100000+10;
int dp1[maxn];
int dp2[maxn];
int a[maxn];

int main() {
    int num = 0, cnt = 1;
    while(cin>>a[num++]) {}
    num--;
    for (int i=0;i<num;i++) {
        dp1[i] = 1;
        dp2[i] = 1;
        for (int j=0;j<i;j++) {
            if (a[i]<a[j]) {
                dp1[i] = max(dp1[i], dp1[j]+1);
            }
            if (a[i]>=a[j]) {
                dp2[i] = max(dp2[i], dp2[j]+1);
            }
        }
    }
    int ans1 = 0, ans2=0;
    for (int i=0;i<num;i++) {
        ans1 = max(ans1, dp1[i]);
    }
    for (int i=0;i<num;i++) {
        ans2 = max(ans2, dp2[i]);
    }
    cout<<ans1<<endl<<ans2<<endl;
    return 0;
}
O（nlogn）（确定low一定是单调递增的）： 
#include <bits/stdc++.h>

using namespace std;

const int max_n = 1e5+100;
const int inf = 30010;
int low[max_n];
int missile[max_n];
string s;

int main() {
    ios::sync_with_stdio(false);
    int n = 0;int ans1, ans2;
    while (cin>>missile[n]) n++;
    fill(low, low+n, inf);
    for (int i=0;i<n;i++) {
        int idx = lower_bound(low, low+n, missile[i])-low;
        low[idx] = missile[i];
    }
    for (int i = n-1;i>=0;i--) {
        if (low[i]!=inf) {
            ans2 = i + 1;
            break;
        }
    }
    reverse(missile, missile+n);
    fill(low, low+n, inf);
    for(int i=0;i<n;i++) {
        int idx = upper_bound(low, low+n, missile[i])-low;
        low[idx] = missile[i];
    }
    for (int i=n-1;i>=0;i--) {
        if (low[i]!=inf) {
            ans1 = i+1;
            break;
        }
    }
    cout<<ans1<<endl<<ans2<<endl;
    return 0;
}