问题一：单调栈 + 二分 O(nlogn)
问题二: 贪心 + 二分 O(nlogn)
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int w[N];
int g[N];
int s[N];//模拟栈
int top;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n = 0;
    int x;
    while(cin >> x && x != EOF && x != 0)
    {
        w[++n] = x;
    }

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


    s[++top] = w[1];
    for(int i = 2;i <= n;i++)//单调栈(栈顶小)
    {
        int l = 1, r = top;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(w[i] > s[mid])r = mid;
            else l = mid + 1;
        }
        if(s[l] < w[i])s[l] = w[i];
        else{
            s[++top] = w[i];
        }       
//      cout << l << " \n";
//      cout << top << " \n";
//      if(i == 4)
//      {
//          for(int i = 1;i <= 4;i++)cout << s[i] << " \n";
//          cout << l << endl;
//      }
    }
    cout << top << endl;

//  int mx = 0;
//  for(int i = 1;i <= n;i++)
//  {
//      mx = max(mx, f[i]);  
//  }
//  cout << mx << endl;

    int cnt = 1;
    g[cnt] = w[1];
    for(int i = 2;i <= n;i++)
    {
        int l = 1, r = cnt;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(g[mid] >= w[i])r = mid;
            else l = mid + 1;
        }

        if(g[l] < w[i])
        {
            g[++cnt] = w[i];
        }
        else{
            g[l] = w[i];
        }
    }
    cout << cnt << endl;

    return 0;
}