javaalgorithmdivide-and-conquer

Please let me know where I am going wrong


This is a program to find maximum subarray using Divide and Conquer.
I keep getting this error:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
ā€‡ ā€‡ at Assignment1.main(Assignment1.java:67)

I think I am passing incorrect variables in the function call but I'm unsure

import java.util.*;

public class Assignment1 {
    public static void main(String[] args){
        
        
        Scanner input = new Scanner(System.in);
        System.out.print("Enter array size: ");
        int size = input.nextInt();
        System.out.println();
        //System.out.print("Enter array elements");
        //System.out.println();
        

        int[] numbers = new int[size];
        for(int i=0; i<numbers.length; i++){
            numbers[i]= i;
        }
        
        int k = numbers[numbers.length];
        int z = numbers[0];
        
        // store the time now
        long startTime = System.nanoTime();
        // linear search for size (which is not in the array)
        int output = bruteForce(numbers);
        System.out.println();
        System.out.print(output);
        System.out.println();
        // display the time elapsed
        System.out.println("The time taken by Linear Search is " + (System.nanoTime() - startTime) + " nanoseconds.");
        
       /// prepare to measure the time elapsed again
        startTime = System.nanoTime();
        // binary search for size
        int y = max_subarray(numbers,z,k);
        System.out.print(y);
        // display the time elapsed
        System.out.println("The time taken by Binary Search is " + (System.nanoTime() - startTime) + " nanoseconds.");
    
    }

    public static int bruteForce(int[] a) {
    int n = a.length;
    int maximumSubArraySum = Integer.MIN_VALUE;
    int start = 0;
    int end = 0;
 
    for (int left = 0; left < n; left++) {
 
        int runningWindowSum = 0;
 
        for (int right = left; right < n; right++) {
            runningWindowSum += a[right];
 
            if (runningWindowSum > maximumSubArraySum) {
                maximumSubArraySum = runningWindowSum;
                start = left;
                end = right;
            }
        }
    }
    return maximumSubArraySum;
    }
    
    public static int max(int a, int b, int c)
    {
    if (a>=b && a>=c)
      return a;
    else if (b>=a && b>=c)
      return b;
    return c;
    }
    
    public static int max_subarray(int[] a, int low, int high) {
    if (high == low)
    {
        return a[high];
    }
    else {
        int mid = ((low+high)/2);
        int leftsum = max_subarray(a,low,mid);
        int rightsum = max_subarray(a,mid+1,high);
        int crosssum = maxCrossingSubarray(a,low,mid,high);
        return max(leftsum,crosssum,rightsum);
    }}
    
    public static int maxCrossingSubarray(int[] a, int low, int mid, int high){
    int leftsum = Integer.MIN_VALUE;
    int sum =0;
    for(int i=mid; i>=low; i--){
    sum += a[i];
    if (sum> leftsum)
    {
        leftsum = sum;
    }}
    
    int rightsum = Integer.MIN_VALUE;
    sum =0;
    for(int j=mid+1; j<=high; j++){
    sum += a[j];
    if (sum> rightsum)
    {
        rightsum = sum;
    }}
    
    return(leftsum+rightsum);
    }
    
}

Solution

  • The issue looks like its here with this code:

     int k = numbers[numbers.length];
     int z = numbers[0];
    

    The correct code for this is, according to my eye at least:

     int k = numbers[numbers.length - 1];
     int z = numbers[0];
    

    Correct this and the code will run. When trying to assign number array length (I input 10 for size and this is used to assign number array to the value of size for testing purposes) to int k, its giving you the array index out of bounds exception because the input is +1 more than the index array length. With the input of 10 the output will be, with the correction:

    OUTPUT: Enter array size: 10

    45 The time taken by Linear Search is 67000 nanoseconds. 45The time taken by Binary Search is 15400 nanoseconds.

    When you input 10, its out of bounds because the array starts at 0 and ends at 9 (when 10 is input by the user). So 10 is out of bounds. To do what youre trying to do, simply minus the 1 from the user input and that will give you the correct assigned length to int k.

    Cheers!