Java Program to find the maximum subarray sum using Binary Search approach

Problem Description

Given an array of integers, find the contiguous subarray, whose sum of the elements, is maximum.
Example:

Array = [2 1 3 5 -2 1 -3 8]

Output:

Subarray = [2 1 3 5 -2 1 -3 8]

Sum = 15

Problem Solution

The idea is to divide the array recursively into two equal parts. Find the middle index of the array, recursively find the maximum sum subarray, in the left part and the right part, find the maximum sum crossing subarray as well, finally return the subarray having the maximum sum.

Program/Source Code

Here is the source code of the Java Program to Find the Maximum Sum in a Contiguous Sub-Array. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

//Java Program to Find the Maximum Sum in a Contiguous Sub-Array
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class MaxSumSubarray {
    //Function to find the maximum sum crossing subarray
    static List<Integer> maxCrossingSubarray(int[] array, int low,int mid,int high)
       {
        int lsum,rsum;
        lsum = rsum = Integer.MIN_VALUE;
        int sum = 0;
        List<Integer> list = new ArrayList<>();
        int i, maxleft, maxright;
        maxleft = maxright = -1;
        for(i=mid;i>=0;i--){
            sum+=array[i];
            if(sum > lsum){
                lsum = sum;
                maxleft = i;
            }
        }
        sum = 0;
        for(i=mid+1;i<=high;i++){
            sum+=array[i];
            if(sum > rsum){
                rsum = sum;
                maxright = i;
            }
        }
        list.add(maxleft);
        list.add(maxright);
        list.add(lsum+rsum);
        return list;
    }
    // Function to recursively find the maximum sum subarray 
    // in left and right subarrays
    static List<Integer> maximumSumSubarray(int[] array, int low, int high){
        List<Integer> list = new ArrayList<>();
        if(low == high){
            list.add(low);
            list.add(high);
            list.add(array[low]);
            return list;
        }
        int mid = (low+high)/2;
        List<Integer> output1 = maximumSumSubarray(array,low,mid);
        List<Integer> output2 = maximumSumSubarray(array,mid+1,high);
        List<Integer> output3 = maxCrossingSubarray(array,low,mid,high);
        if(output1.get(2) >= output2.get(2) && output1.get(2) >= output3.get(2))
            return output1;
        else if (output2.get(2) >= output1.get(2) && 
                 output2.get(2) >= output3.get(2))
            return output2;
        return output3;
    }
    // Function to read user-input and display the output
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size;
        System.out.println("Enter the size of the array");
        try {
            size = Integer.parseInt(br.readLine());
        } catch (Exception e) {
            System.out.println("Invalid Input");
            return;
        }
        int[] array = new int[size];
        System.out.println("Enter array elements");
        int i;
        for (i = 0; i < array.length; i++) {
            try {
                array[i] = Integer.parseInt(br.readLine());
            } catch (Exception e) {
                System.out.println("An error Occurred");
            }
        }
        List<Integer> output = maximumSumSubarray(array, 0, array.length-1);
        System.out.println("The maximum sum subarray is");
        int x = 0;
        Iterator<Integer> it = output.getIterator();
        for(Integer i : it){
            System.out.print(i + " ");
            x+=i;
        }
        System.out.println("nThe maximum sum is " + x);
    }
}

Program Explanation

1. In the function maxCrossingSubarray(), the variables lsum and rsum are initialized to Integer.MIN_VALUE.
2. The loop for(i=mid;i>=0; i–) is used to find the maximum sum contiguous subarray in the left half, moving from the index mid to low.
3. The variable maxleft stores the index of the leftmost element to be included in the crossing subarray.
4. The loop for(i=mid+1;i<=high; i++) is used to find the maximum sum contiguous subarray in the right half, moving from the index mid+1 to high.
5. The variable maxright stores the index of the leftmost element to be included in the crossing subarray.
6. The list is returned, which consists of maxleft, maxright and (lsum+rsum), which is the sum of the crossing subarray.
7. In function maximumSumSubarray(), the condition if(low == high) checks if there is only one element in the array, it returns the element if it is true.
8. Otherwise, the index of the middle element is calculated and the function is recursively called on left and right halves and the function maxCrossingSubarray() is called.
9. The return values of the three functions are compared and the largest of them is returned.

Time Complexity: O(n*log(n)) where n is the number of elements in the array.

Runtime Test Cases

Case 1 (Simple Test Case):
 
Enter the size of the array
8
Enter array elements
2
1
3
5
-2
1
-3
8
The maximum sum subarray is
2 1 3 5 -2 1 -3 8 
The maximum sum is 15
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
7
Enter array elements
3
-4
2
-3
-1
7
-5
The maximum sum subarray is
7 
The maximum sum is 7