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
}