Maximum in a array with divide and conquer

4
votes

Premise that this is homework, and I don't know why I can't use the tag 'homework', so I'll write it down here for clarity.

I have to write a method "int maximum(int[] a, int l, int r)" that finds the maximum in the array A spanning from 'l' to 'r' using a Divide and Conquer approach. Base Case will be when A has a single element inside, so if A.length == 1, return the element. The recursive part should divide the array in two subarrays spanning from A[l] to A[mid], and from A[mid+1] to A[r]. In theory I'm ok with that, but I keep getting a StackOverflowError and I don't understand why.

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;
}
}
2
javaarraysalgorithm
You can't write the homework tag because homework is not allowed - Small Legend
@SmallLegend Homework is allowed, but it requires that attempted code is shown and the question is well specified. Questions asking to do homework without any code, as well as questions containing code but not a specific question however are off-topic. - Kayaman
ah news to me thank you @Kayaman and I apologise Monok - Small Legend
No need to apologise, we're all here to teach and learn. I also understood why I couldn't, so thanks @Kayaman - Monok
It's very simple, asking a good question is allowed regardless of the "intention". The issue is that homework questions are often low quality (classic example is a "question" containing nothing but the homework assignment), but that doesn't mean that homework questions per se are off-topic for SO. - Kayaman

2 Answers

10
votes

You have a problem in the calculation of mid.

It should be

int mid = (l+r)/2;

Beside that,

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

should be

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

since you are always passing the original array to your method, so A.length can only be 1 if the original array has a single element.

2
votes

In Divide and Conquer approach when we calculating index of mid element, that mean is sum of first and last index divide by 2.

Also, when left element index is same as right element index then it means array has one element and then only we return that single array element.

your solution is : 

 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;
}}