Maximum in a array with divide and conquer

Question

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

You can't write the homework tag because homework is not allowed — Small Legend
– Small Legend, Commented Jun 15, 2016 at 8:44
@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
– Kayaman, Commented Jun 15, 2016 at 8:46
No need to apologise, we're all here to teach and learn. I also understood why I couldn't, so thanks @Kayaman — Monok
– Monok, Commented Jun 15, 2016 at 8:50
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
– Kayaman, Commented Jun 15, 2016 at 8:54

Eran · Accepted Answer · 2016-06-15 08:49:33Z

10

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.

edited Jun 15, 2016 at 8:49

answered Jun 15, 2016 at 8:46

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Monok Over a year ago

Oh my, now it works!! Thank you very much! Can you give me a detailed explanation of my error?

Eran Over a year ago

@Monok If you want to find the middle index in the range [l,r], it is not r/2. It is (l+r)/2. It will only be r/2 if l==0. As for the stopping condition, I added an explanation to the answer.

Monok Over a year ago

Understood perfectly, thanks again. I didn't realize that if I have a range I already know how to calculate the mid, so I tried to find another - wrong - way to do it.

UDID · Accepted Answer · 2016-06-15 09:44:29Z

2

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

answered Jun 15, 2016 at 9:44

UDID

2,4233 gold badges18 silver badges32 bronze badges

3 Comments

Spartan Over a year ago

you deserve 2k :)

SunnyBoiz Over a year ago

Hey, I am trying to understand this. May I know the reason why the maxRight will need to +1 for mid+1? Thank you.

UDID Over a year ago

maxRight is new low for the other half, so for other half mid+1 is low and r is High.

Collectives™ on Stack Overflow

Maximum in a array with divide and conquer

2 Answers 2

3 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related