算法一：记录全局最小值

import java.util.*;
class Main{
    private static int ans, n;
    private static int[] a, up, down;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        while(n > 0){
            a = new int[n+1];
            for(int i = 1; i <= n; i++){
                a[i] = sc.nextInt();
            }
            up = new int[n+1];
            down = new int[n+1];
            ans = n;
            dfs(1, 0, 0);           //下标从1开始搜索
            System.out.println(ans);
            n = sc.nextInt();
        }
    }
    private static void dfs(int u, int su, int sd){
        if(su + sd >= ans) return;
        if(u == n+1){               //n+1表示前n个已经遍历到可以结束
            ans = Math.min(ans, su + sd);
            return;
        }
        //加入到上升子序列当中
        int k = 0;
        while(k < su && up[k] <= a[u]) k++;
        if(k == su){
            up[k] = a[u];           //相等时第一次赋值所以不需要恢复现场
            dfs(u+1, su+1, sd); 
        }else{
            int t = up[k];
            up[k] = a[u];
            dfs(u+1, su, sd);
            up[k] = t;
        }
        //加入到下降子序列当中
        k = 0;
        while(k < sd && down[k] >= a[u]) k++;
        if(k == sd){
            down[k] = a[u];
            dfs(u+1, su, sd+1);
        }else{
            int t = down[k];
            down[k] = a[u];
            dfs(u+1, su, sd);
            down[k] = t;
        }
    }
}

算法二：迭代加深

import java.util.*;
class Main{
    private static int n;
    private static int[] a, up, down;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        while(n > 0){
            a = new int[n+1];
            for(int i = 1; i <= n; i++){
                a[i] = sc.nextInt();
            }
            up = new int[n+1];
            down = new int[n+1];
            int depth = 0;
            while(!dfs(depth, 1, 0, 0)) depth++;
            System.out.println(depth);
            n = sc.nextInt();
        }
    }
    private static boolean dfs(int depth, int u, int su, int sd){
        if(su + sd > depth) return false;
        if(u == n+1) return true;
        //放入到最长上升子序列中
        int k = 0;
        while(k < su && up[k] <= a[u]) k++;
        if(k == su){
            up[k] = a[u];
            if(dfs(depth, u+1, su+1, sd)) return true;
        }else{
            int t = up[k];
            up[k] = a[u];
            if(dfs(depth, u+1, su, sd)) return true;
            up[k] = t;
        }
        //放入到下降子序列中
        k = 0;
        while(k < sd && down[k] >= a[u]) k++;
        if(k == sd){
            down[k] = a[u];
            if(dfs(depth, u+1, su, sd+1)) return true;
        }else{
            int t = down[k];
            down[k] = a[u];
            if(dfs(depth, u+1, su, sd)) return true;
            down[k] = t;
        }
        return false;
    }
}