使用分治算法寻找数组中的最大值

Question

使用分治算法寻找数组中的最大值

4

基于这是一道作业题，我不知道为什么不能使用“作业”标签，所以我在此清晰地写下。

我需要编写一个方法 "int maximum(int [] a, int l, int r)" ，使用分治法查找从'l'到'r'的数组A中的最大值。基本情况是当A中只有一个元素时，如果A.length == 1，则返回该元素。递归部分应将数组分成两个子数组，从A [l]到A [mid]，从A [mid + 1]到A [r]。理论上我没问题，但我一直得到 StackOverflowError 错误，我不明白为什么。

public class Maximum {
public static void main(String[] args) {
    int[] A = {0, 5, 281, 3, 9, 4, 88, 16, 17, 60};
    int l = 0;
    int r = A.length-1;
    System.out.println("Maximum of the array: "+maxArray(A, l, r));
}
public static int maxArray(int[] A, int l, int r) {

    //Assuming that the index of array is '0' and not '1', l is 0. Else, put 1.

    if (A.length == 1) {
        return A[l];
    }

    int mid = r/2;
    int maxLeft = 0;
    int maxRight = 0;

    maxLeft = maxArray(A, l, mid);        //Here is the StackOverflowError!
    maxRight = maxArray(A, mid+1, r);

    if (maxLeft < maxRight) {
        return maxRight;
    } else 
return maxLeft;
}
}

- Monok

你不能写作业标签，因为不允许出现作业相关内容。 - Small Legend

@小传奇作业是允许的，但需要展示尝试的代码并明确问题。询问如何完成作业但没有提供任何代码，以及包含代码但没有具体问题的问题都属于不适合讨论的范畴。 - Kayaman

啊，这对我来说是个好消息，谢谢@Kayaman，同时我向Monok道歉。 - Small Legend

不用道歉，我们都在这里教学互相学习。我也明白了为什么我不能做到，所以感谢@Kayaman。 - Monok

非常简单，无论“意图”如何，都可以提出一个好问题。问题在于作业问题通常质量较低（经典例子是仅包含作业任务的“问题”），但这并不意味着作业问题本身就不适用于SO。 - Kayaman

2个回答

2

在“分而治之”方法中，当我们计算中间元素的索引时，即为第一个和最后一个索引的和除以2。

此外，当左侧元素索引与右侧元素索引相同时，这意味着数组只有一个元素，然后我们才返回该单个数组元素。

您的解决方案是：

 public class Helloworld{

 public static void main(String []args){
  int[] A = {0, 5, 281, 3, 9, 4, 88, 16, 17, 60};
int l = 0;
int r = A.length-1;
System.out.println("Maximum of the array: "+maxArray(A, l, r));
 }

 public static int maxArray(int[] A, int l, int r) {

//Assuming that the index of array is '0' and not '1', l is 0. Else, put 1.

if (l == r) { // checking codition/
    return A[l]; 
}

int mid = (l+r)/2; // Calculating mid.
int maxLeft = 0;
int maxRight = 0;

maxLeft = maxArray(A, l, mid);        
maxRight = maxArray(A, mid+1, r);

if (maxLeft < maxRight) {
    return maxRight;
} else return maxLeft;
}}

- UDID

你值得2k :) - Spartan

嗨，我正在努力理解这个问题。请问为什么maxRight需要在mid+1时加1呢？谢谢。 - SunnyBoiz

maxRight 是另一半的新低，因此对于另一半来说 mid+1 是低位，r 是高位。 - UDID

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eran · Accepted Answer

你在计算mid时遇到了问题。

正确的计算方式应该是

int mid = (l+r)/2;

除此之外，

if (A.length == 1) {
    return A[l];
}

应该是

if (l == r) {
    return A[l];
}

因为你总是将原始数组传递给你的方法，所以A.length只有在原始数组只有一个元素时才会为1。