下标从0开始

import java.util.*;

public class Main {
    static final int N = 55;
    static int[] a = new int[N], up = new int[N], down = new int[N];
    static int n, ans;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        while (true) {   
            n = Integer.parseInt(sc.nextLine());
            if (n == 0) break;
            String[] s = sc.nextLine().split(" ");
            for (int i = 0; i < n; i++) a[i] = Integer.parseInt(s[i]);

            ans = n;//记录最坏情况，这里可以把ans初始化为一个>=n的任意整数都可以
            dfs(0, 0, 0);

            System.out.println(ans);
        }
    }

    /**
    * u : 当前开始枚举第几个点(a[u]下标从0开始的)
    * su : 当前上升子序列的个数
    * sd : 当前下降子序列的个数
    */
    static void dfs(int u, int su, int sd) {
        if (su + sd >= ans) return;//剪枝
        if (u == n) {
            ans = su + sd;//第一个判断已经进行去max了
            return;
        }

        //第一种情况,将a[u]放在上升子序列中
        int k = 0; 
        while (k < su && a[u] <= up[k]) k++;//这里是严格单调的子序列,因此需要添加等号(跳过=)
        int t = up[k];//记录当前up[k]状态方便恢复现场
        up[k] = a[u];
        if (k < su) dfs(u + 1, su, sd);//没有超过序列个数
        else dfs(u + 1, su + 1, sd);//超过序列个数
        up[k] = t;//恢复现场

        //第二种情况,将a[u]放在下降子序列中
        k = 0;
        while (k < sd && a[u] >= down[k]) k++;
        t = down[k];
        down[k] = a[u];
        if (k < sd) dfs(u + 1, su, sd);
        else dfs(u + 1, su, sd + 1);
        down[k] = t;
    }
}

从1开始

import java.util.*;

public class Main {
    static final int N = 55;
    static int[] a = new int[N], up = new int[N], down = new int[N];
    static int n, ans;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        while (true) {   
            n = Integer.parseInt(sc.nextLine());
            if (n == 0) break;
            String[] s = sc.nextLine().split(" ");
            for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(s[i - 1]);

            ans = n;
            dfs(1, 0, 0);

            System.out.println(ans);
        }
    }

    static void dfs(int u, int su, int sd) {
        if (su + sd >= ans) return;
        if (u == n + 1) {
            ans = su + sd;
            return;
        }

        int k = 0; 
        while (k < su && a[u] <= up[k]) k++;
        int t = up[k];
        up[k] = a[u];
        if (k < su) dfs(u + 1, su, sd);
        else dfs(u + 1, su + 1, sd);
        up[k] = t;

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