如何在没有索引的情况下找到递归数组的maxim值？

Question

我有一个valorMaxim([1, 5, 252, 24, 7, 82, 3])返回252号的方法。我不知道怎么做。我一直在想，如果我能减少数组长度。

public static int valorMaxim(int arr[]){
    int max;

    if(arr.length==1)
        return arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] < arr[i+1]) {
            max=arr[i+1];
            return arr[i+1];
        }
    }
    return valorMaxim(arr);

    //Retorna el valor màxim en un array no buit d’enters.
}

Answer 1

我将接受的答案修改为Finding Max value in an array using recursion。

正如您所建议的(即每次递归方法调用时减少数组长度)，我创建一个方法参数的副本，其长度比参数少一个，并删除第一个元素。然后递归地使用数组副本调用该方法。

public class Main {

    public static int valorMaxim(int arr[]){
        if (arr.length == 1) {
            return arr[0];
        }
        else {
            int[] tmp = new int[arr.length - 1];
            System.arraycopy(arr, 1, tmp, 0, tmp.length);
            return Math.max(arr[0], valorMaxim(tmp));
        }
    }

    public static void main(String[] args) {
        System.out.println(valorMaxim(new int[]{1, 5, 252, 24, 7, 82, 3}));
    }
}

Answer 2

基本上，递归的思想是：

如果数组的长度为1，则返回唯一的element;

• Otherwise，将数组拆分为第一个元素，并将其他元素拆分为xs；

• 在xs中找到最大元素，将其与x进行比较并生成更大的。

有两种方法可以实现这种“分裂”：

1. 为xs创建部分数组的新副本

您可以使用System.arraycopy (请参阅@Abra的答案)或Arrays.copyOfRange，这更简单：

int[] xs = Arrays.copyOfRange(arr，1，arr.length)；

现在我们查找xs中的最大元素(即valorMaxim(xs))，并将其与x进行比较，作为最终结果：

返回Math.max(x，valorMaxim(xs))；

把所有东西放在一起，别忘了添加一个长度检查器：

公共静态int valorMaxim(int arr[]) { if (arr.length == 1)返回arr；int x= arr；int[] xs = Arrays.copyOfRange(arr，1，arr.length)；返回Math.max(x，valorMaxim(xs))；}

就这样！因为首先我们有长度检查器，所以我们可以安全地确保ArrayIndexOutOfBoundsException.不会是空的，因此valorMaxim(xs)永远不会导致xs。

1. 为数组设置边界

您可能已经发现，每次复制一个新数组可能会耗费时间和内存。与其为xs创建物理副本，我们还可以概念化这个想法并使用有界数组。为此，我们需要定义一个助手方法：

私有静态int findMaxBound(int arr[]，int startFrom) { // "xs“有长度1吗？如果(startFrom == arr.length - 1)返回arrstartFrom；int x= arrstartFrom；int maxInXs = findMaxBound(arr，startFrom + 1)；返回Math.max(x，maxInXs)；}

然后我们可以将valorMaxim定义为

公共静态int valorMaxim(int arr[]) {返回findMaxBound(arr，0)；}

最后，我们没有创建arr的任何新副本，而是在整个过程中使用不同的范围并将它们作为xs对待。