(暴力+dfs) $O(n^2)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100;
int a[maxn];
int n, ans;
int up[maxn], down[maxn]; //存上升序列每个序列最后一个数字，下降序列每个序列最后一个数字

void dfs(int i, int su, int sd)// dfs到第i个数字，有su个上升序列，sd个下降序列
{
    if(su + sd >= ans) return;//如果序列个数等于数组个数返回
    if(i == n)//如果循环到最后一个数字 更新总数组数，返回
    {
        ans = su + sd;
        return;
    }
    // up array 当前数组准备放到上升数组中
    int k = 0;  
    while(k < su && up[k] >= a[i]) k ++;      //如果当前数字比第k个序列的最后一个数字小，则不能放进去，就循环下一个上升序列
    int t = up[k];// 因为是dfs 所以保存一下，方便回溯
    up[k] = a[i];  //更新第k个上升序列的最后一个数字为a[i]
    if(k < su) dfs(i+1, su, sd);// 如果没有增加新的序列，则dfs
    else dfs(i+1, su+1, sd); //增加了 则dfs  
    up[k] = t;// 回溯

    // down array
    k = 0;
    while( k < sd && down[k] <= a[i]) k ++;
    t = down[k];
    down[k] = a[i];
    if(k < sd) dfs(i+1, su, sd);
    else dfs(i+1, su, sd+1);
    down[k] = t;
}

int main()
{
    while(scanf("%d",&n) && n)
    {
        for(int i = 0; i < n; i ++)
        {
            cin >> a[i];
        }
        ans = n;
        dfs(0,0,0);
        cout << ans << endl;
    }
    return 0;
}