使用递归查找数组中的最大值

Question

在我被要求解决的问题中，我使用for循环找到了数组的最大值，因此我尝试使用递归来找到它，以下是我的方法：

public static int findMax(int[] a, int head, int last) {

    int max = 0;
    if (head == last) {
        return a[head];
    } else if (a[head] < a[last]) {
        return findMax(a, head + 1, last);
    } else {
        return a[head];
    }
}

它能正常运行并获得最大值，但我的问题是：基本情况下返回a [head]是否可以，如果头部的值大于最后一个值怎么办？

- Scarl

---

是的，我做了，并且它有效。 - Scarl

这并不是你的错，但是通过递归在数组中查找最大值是完全愚蠢的。这是对递归技术的误用。 - AlexWien

我基本上知道如何使用for循环获取最大值，所以我想尝试使用递归来编写代码。 - Scarl

如果head=0且last=2，则对于数组{2,42,1}，该方法应该失败，因为它将返回2而不进行递归。 - Ingo

@Ingo 实际上返回的是 42，作为最大值。编辑：不好意思，你是对的！ - Scarl

我认为我应该编辑代码，从else return head到else return findMax(a,head,last-1)。 - Scarl

Answer 1

你同样可以只使用一个计数器，即要比较的值的索引：

public static int findMax(int[] a, int index) {
    if (index > 0) {
        return Math.max(a[index], findMax(a, index-1))
    } else {
        return a[0];
    }
}

这更清楚地显示了正在发生的事情，并使用默认的“递归”布局，例如具有通用基本步骤。初始调用通过执行 findMax（a，a.length-1） 实现。

- Joost

---

if(index)不能编译 ;) - Thomas Jungblut

实际上，我使用了两个计数器来跟踪索引，就像头计数器将向数组末尾移动一样。在您的答案中，我不明白为什么要使用Math.max。 - Scarl

@ThomasJungblut 谢谢。我通常不编写Java程序，幸运的是 :) - Joost

Math.max 基本上就是你的 if (a[head] < a[last]) 所做的事情。这基本上是分而治之，你只处理当前索引和其余部分（递归调用）的结果，并将它们合并以得到所需的答案。在这种情况下，您想要它们中的最大值，因此您使用 Math.max 进行合并。 - Joost

为什么要检查索引是否大于0？可以先添加基本情况。 - Ahmed Emad

Answer 2

实际上，这比那更简单。基本情况是如果您已经到达数组的末尾（下面三元控制块的“else”部分）。否则，您将返回当前值和递归调用的最大值。

public static int findMax(int[] a) {
    return findMax(a, 0);
}
private static int findMax(int[] a, int i) {
    return i < a.length
           ? Math.max(a[i], findMax(a, i + 1))
           : Integer.MIN_VALUE;
}

对于每个元素，您返回当前元素和所有具有更大索引的元素中较大的元素。仅在空数组上返回Integer.MIN_VALUE。此操作以线性时间运行。

- azz

Answer 3

我会通过在每个递归调用中将数组分成两半来解决这个问题。

 findMax(int[] data, int a, int b)

其中a和b是数组的索引。

停止条件是b - a <= 1，此时它们是相邻的，最大值为max(a,b)；

初始调用：

 findMax(int[] data, int 0, data.length -1);

这将把最大递归深度从N降至log2(N)。但搜索工作仍然是O(N)。

这将导致：

int findMax(int[] data, int a, int b) {
   if (b - a <= 1) {
     return Math.max(data[a], data[b]);
   } else {
     int mid = (a+b) /2; // this can overflow for values near Integer.Max: can be solved by a + (b-a) / 2; 
     int leftMax =  findMax(a, mid);
     int rightMax = findMax(mid +1, b);
     return Math.max(leftMax, rightMax);
   }
}

- AlexWien

---

唯一的优化是减少堆栈开销，但复杂度仍然是相同的（O(n)）。 - azz

确实，@DerFlatulator。因为在这里，“树”的两侧都被访问了，所有的n个元素都被访问了，时间复杂度为O(n)。它类似于二分查找，但是这种相似性是误导人的，因为对于二分查找，只有“树”的一侧被访问，可以在O(log n)步骤内到达平衡树中最深的元素。 - Joost

是的，这确实是唯一的优化，但它增加了可能的数组大小；但这仍然是一个愚蠢的问题；他们应该学习递归二分查找。 - AlexWien

@Joost 已更新以纳入您的评论。 - AlexWien

无论如何，使用递归搜索一个常规数组并没有什么意义。因此，当你可以切换到迭代方法时，试图优化它似乎是徒劳的。 - azz

我知道二分查找算法，但我只是想写出使用递归查找最大值的代码。 - Scarl

Answer 4

我看到了这个帖子，它对我很有帮助。以下是我完整的代码，包括递归和分治两种情况。 在分治情况下，运行时间略优于递归。

//use divide and conquer.
public int findMaxDivideConquer(int[] arr){
    return findMaxDivideConquerHelper(arr, 0, arr.length-1);
}
private int findMaxDivideConquerHelper(int[] arr, int start, int end){
    //base case
    if(end - start  <=  1) return Math.max(arr[start], arr[end]);
    //divide
    int mid = start + ( end - start )/2;
    int leftMax =findMaxDivideConquerHelper(arr, start, mid);
    int rightMax =findMaxDivideConquerHelper(arr, mid+1, end);
    //conquer
    return Math.max( leftMax, rightMax );
}

// use recursion. return the max of the current and recursive call
public int findMaxRec(int[] arr){
    return findMaxRec(arr, 0);
}
private int findMaxRec(int[] arr, int i){
    if (i == arr.length) {
        return Integer.MIN_VALUE;
    }
    return Math.max(arr[i], findMaxRec(arr, i+1));
}

- rrr

Answer 5

我知道这是一个旧的线程，但也许这可以帮助！

public static int max(int[] a, int n) {
        if(n < 0) {
            return Integer.MIN_VALUE;
        }
        return Math.max(a[n-1], max(a, n - 2));

    }

- user6694478

Answer 6

class Test
{
    int high;
    int arr[];
    int n;
    Test()
    {
        n=5;
        arr = new int[n];
        arr[0] = 10;
        arr[1] = 20;
        arr[2] = 30;
        arr[3] = 40;
        arr[4] = 50;
        high = arr[0];
    }
    public static void main(String[] args)
    {
       Test t = new Test();
       t.findHigh(0);
       t.printHigh();
    }
    public void printHigh()
    {
        System.out.println("highest = "+high);
    }
    public void findHigh(int i)
    {
        if(i > n-1)
        {
            return;
        }
        if(arr[i] > high)
        {
            high = arr[i];
        }
        findHigh(i+1);
        return;
    }
}

- Ghulam Moinul Quadir

Answer 7

这个怎么样？

public static int maxElement(int[] a, int index, int max) {
    int largest = max;
    while (index < a.length-1) {
        //If current is the first element then override largest
        if (index == 0) {
            largest = a[0];
        }
        if (largest < a[index+1]) {
            largest = a[index+1];
            System.out.println("New Largest : " + largest); //Just to track the change in largest value
        }
        maxElement(a,index+1,largest);
    }
    return largest;
}

- Recomer

Answer 8

这不行！您的代码无法找到数组中的最大元素，它只会返回比其相邻元素更高值的元素，为了解决这个问题，可以将范围内的最大值元素作为递归方法的参数进行传递。

    private static int findMax(int[] a, int head, int last,int max) {
    if(last == head) {
        return max;
    }
    else if (a[head] > a[last]) {
            max = a[head];
            return findMax(a, head, last - 1, max);
        } else {
            max = a[last];
            return findMax(a, head + 1, last, max);
        }
}

- Learnaholic

Answer 9

感谢@Robert Columbia 的建议！

更新：这个函数将从索引0开始递归，并将继续将其添加到此索引值，直到它等于数组的长度，如果更多，我们应该停止并返回0。完成此操作后，我们需要获取数组中每两个项目的最大值，例如：

A = [1 , 2 , 3 ];

A[0] ( 1 ) vs A[1] ( 2 ) = 2 
A[1] ( 2 ) vs A[2] ( 3 ) = 3
Max(2,3) = 3 ( The answer )  





public int GetMax(int [] A, int index)  {

     index += 1;
     if (index >= A.Length) return 0;
     return Math.Max(A[index], GetMax(A, index + 1));

 }

- Khaled Saleh

---

虽然这份代码可能能够回答问题，但最好解释一下如何解决问题并提供代码作为参考。只给出代码的答案通常缺乏实用性，会令人困惑。 - Robert Columbia

Answer 10

私有静态整型 getMax(int[] arr, int idx) {

    if (idx==arr.length-1 ) return arr[idx];

    
    return Math.max(arr[idx], getMax (arr,idx+1 ));
}

- Ahmed Emad