巧用递归解决选择问题

题目

1) 给定一个数组,可以将任意一个数字标记为红色或者蓝色,使得所有红色数字递增,蓝色数字递减;
判断是否可以将所有数字都染色
例子:
输入:

输出:

解释

解答

public class blueRed {
    public static void main(String[] args) {
        int[] arr = new int[]{7, 4, 1, 3, 2, 5, 6};
        System.out.println(new blueRed().isFinish(arr));
    }
    public boolean isFinish(int[] arr) {
        boolean red1 = dfs(arr, 1, arr[0], Integer.MAX_VALUE); // 如果将第一个元素标为红色
        boolean blue1 =dfs(arr, 1, Integer.MIN_VALUE, arr[0]); // 如果将第一个元素标为蓝色
        return  red1 || blue1; 
    }
    /**
     * @param arr 
     * @param index 当前搜索的数字索引
     * @param lower 升序序列的末尾
     * @param higher 降序序列的末尾
     */
    public boolean dfs(int[] arr, int index, int lower, int higher) {
        if (index >= arr.length) return true;
        System.out.println("当前的index "+arr[index]+" lower "+lower+" higher "+higher);
        if (arr[index] > lower) {
            System.out.println("当前"+arr[index]+"如果升序末尾的话");
            if (dfs(arr, index + 1, arr[index],higher)){
                System.out.println("最终 red "+arr[index]);
                return true;
            }
        }
        if (arr[index] < higher) {
            System.out.println("当前"+arr[index]+"如果降序末尾的话");
            if (dfs(arr, index + 1, lower, arr[index])){
                System.out.println("最终 blue "+arr[index]);
                return true;
            }
        }
        System.out.println(arr[index]+"不能继续标了 需回退上一个重新做决定");
        return false;
    }
}

:::info 当前1如果降序末尾的话
当前的index 3 lower 4 higher 1
3不能继续标了 需回退上一个重新做决定
1不能继续标了 需回退上一个重新做决定
当前4如果降序末尾的话
当前的index 1 lower -2147483648 higher 4
当前1如果升序末尾的话
当前的index 3 lower 1 higher 4
当前3如果升序末尾的话
当前的index 2 lower 3 higher 4
当前2如果降序末尾的话
当前的index 5 lower 3 higher 2
当前5如果升序末尾的话
当前的index 6 lower 5 higher 2
当前6如果升序末尾的话
最终 red 6
最终 red 5
最终 blue 2
最终 red 3
最终 red 1
最终 blue 4
true :::