字节面试题：给定数字n，数组arr={1,3,5,2}，求arr中的数字能组成小于n的最大整数

    // 算法流程详见dfs函数，设数字n有m位，arr长度为n,时间复杂度O(m*n)public int max(int n, int[] arr) {Arrays.sort(arr);String value = String.valueOf(n);char[] chars = value.toCharArray();int[] nums = new int[chars.length];for (int i = 0; i < nums.length; i++) {nums[i] = Integer.parseInt(String.valueOf(chars[i]));}return dfs(arr, nums, true, 0);}/**** @param arr* @param nums* @param preEq 前一个位置取值是否等于nums[index]* @param index 当前考虑index位置* @return 返回最大的组合值*/public int dfs(int[] arr, int[] nums, boolean preEq, int index) {if (index == nums.length) {return 0;}if (preEq) {//目标：因为找的是最大但小&最接近，所以从最高位开始找，找到第一个小的即可//而对于找比n大的下一个数，自然是从最低位找。找到第一个小的，然后翻转前面大但小的。// 条件1.index位置的取值必须满足arr[i] <= nums[index]//找小于n的最大数，自然是选的数要比n的当前位要小啊，逼近//1:没有找到：即都是比n大的，那就return -1//2:找的都是相等的：判断一下：那就继续向前便利，看是否存在一个小的，如果没有那相等也不符合题意//3:   //高位发现一个小的了，那后面的低位全部取最大值即可for (int i = arr.length - 1; i >= 0; i--) {if (arr[i] <= nums[index]) {//贪心策略：有等于的数字优先取等于，没有的话取小于//判断当前这个是否能入选，先试一下dfsint i1 = (int) (arr[i] * Math.pow(10, nums.length - index - 1) + dfs(arr, nums, arr[i] == nums[index], index + 1));if (i1 == -1 && arr[i] == nums[index]) {continue;}//这个能入选，所以dfs下一个，returnreturn (int) (arr[i] * Math.pow(10, nums.length - index - 1) + dfs(arr, nums, arr[i] == nums[index], index + 1));}}if (index == 0) {// 第一个没有满足小于等于的条件，舍弃第一位//因为没办法，同样数位的，没有比n小的，只能降低一位了return dfs(arr, nums, false, index + 1);}return -1;} else {/ /第一个没有满足小于等于的条件，舍弃第一位后，全部走这个流程return (int) (arr[arr.length - 1] * Math.pow(10, nums.length - index - 1) + dfs(arr, nums, false, index + 1));}}