C++ 代码

// 1.使用dfs是因为方便剪枝和减少空间复杂度
// 2.为什么用dfs,因为对于每种数都有两种选择,要么存在于上升子序列中,要么在下降子序列中
// 需要搜索所有的情况,并找到最小值

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 55;

int w[N];
int up[N];
int down[N];
int n;

bool dfs(int depth, int u, int sd, int su)
{
    if(sd + su > depth) return false;
    if(u == n) return true;

    int k = 0;
    while(k < su && up[k] >= w[u]) k ++;
    int t = up[k];
    up[k] = w[u];
    if(k < su && dfs(depth, u + 1, sd, su)) return true;
    else if(k >= su && dfs(depth, u + 1, sd, su + 1)) return true;
    up[k] = t;

    k = 0;
    while(k < sd && down[k] <= w[u]) k ++;
    t = down[k];
    down[k] = w[u];
    if(k < sd && dfs(depth, u + 1, sd, su)) return true;
    else if(k >= sd && dfs(depth, u + 1, sd + 1, su)) return true;
    down[k] = t;

    return false;
}

int main()
{
    while(cin >> n, n)
    {
        for(int i = 0; i < n; i ++) cin >> w[i];

        int depth = 1;
        while(!dfs(depth,0,0,0)) depth ++;

        cout << depth << endl;
    }
    return 0;
}