I'm getting the error ArrayIndexOutOfBoundsException: index -25 out of bonds for length 16

Viewed 12

This is my current code for a program to find the maximum subarray. I am getting the out of bounds error for 3 lines: I'm getting the error ArrayIndexOutOfBoundsException: index -25 out of bonds for length 16. I'm testing it with the array int[]{13,-3,-25,-20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7}. I've only seen this error when using the wrong numbers for iterating through arrays in for loops, so I'm not sure what is causing it here.

static int findHigh(int[] arr) {
    int high = arr[0];
    for(int i = 0; i < arr.length; i++) {
        if(arr[i] >= high)
            high = arr[i];
    }
    return high;
}
static int findLow(int[] arr) {
    int low = arr[0];
    for(int i = 0; i < arr.length; i++) {
        if(arr[i] <= low)
            low = arr[i];
    }
    return low;
}

static Triple<Integer,Integer,Integer> findMaxSubarray(int[] arr, int low, int high){
    
    if(high == low)
        return (new Triple<> (low, high, arr[low])); //error here
    else {
        int mid = low + (high - low) / 2;

        Triple<Integer,Integer,Integer> l = findMaxSubarray(arr, low, mid); //error here
        Triple<Integer,Integer,Integer> r = findMaxSubarray(arr, mid + 1, high);
        Triple<Integer, Integer, Integer> c = findMaxCrossingArray(arr, low, mid, high);
        
        if(l.getLast() >= r.getLast() && l.getLast() >= c.getLast())
            return (new Triple<> (l.getFirst(), l.getMiddle(), l.getLast()));
        else if(r.getLast() >= l.getLast() && r.getLast() >= c.getLast())
            return (new Triple<> (r.getFirst(), r.getMiddle(), r.getLast()));
        else
            return (new Triple<> (c.getFirst(), c.getMiddle(), c.getLast()));
    }
}

static Triple<Integer,Integer,Integer> findMaxCrossingArray(int arr[], int low, int mid, int high){
    int leftSum = Integer.MIN_VALUE, leftMax = 0;
    int rightSum = Integer.MIN_VALUE, rightMax = 0;
    int sum = 0;
    for(int i = mid; i >= low; i--) {
        sum += arr[i];
        if (sum > leftSum) {
            leftSum = sum;
            leftMax = i;
        }
    }
    sum = 0;
    for(int j = mid; j <= high; j++) {
        sum += arr[j];
        if (sum > rightSum) {
            rightSum = sum;
            rightMax = j;
        }
    }
    return (new Triple<> (leftMax, rightMax, leftSum + rightSum));
}

public static Triple<Integer,Integer,Integer> getMaxSubarray(int[] arr){
    int high = findHigh(arr);
    int low = findLow(arr);
    
    return(findMaxSubarray(arr, low, high)); //error here
}
1 Answers

When you use

 return (new Triple<> (low, high, arr[low]));

It take arr[index] in the third place, so if your lowest number is -25 it is causing bug with out of bonds, cause your index is -25.

Related