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

«
»

This is the Java Program to Find the Maximum Sum in a Contiguous Sub-Array.

Problem Description

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

advertisement

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

Output:

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

advertisement
advertisement

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.

advertisement
  1.  
  2. //Java Program to Find the Maximum Sum in a Contiguous Sub-Array
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.InputStreamReader;
  6.  
  7. public class MaxSumSubarray {
  8.     //Function to find the maximum sum crossing subarray
  9.     static List<Integer> maxCrossingSubarray(int[] array, int low,int mid,int high)
  10.        {
  11.         int lsum,rsum;
  12.         lsum = rsum = Integer.MIN_VALUE;
  13.         int sum = 0;
  14.         List<Integer> list = new ArrayList<>();
  15.         int i, maxleft, maxright;
  16.         maxleft = maxright = -1;
  17.         for(i=mid;i>=0;i--){
  18.             sum+=array[i];
  19.             if(sum > lsum){
  20.                 lsum = sum;
  21.                 maxleft = i;
  22.             }
  23.         }
  24.         sum = 0;
  25.         for(i=mid+1;i<=high;i++){
  26.             sum+=array[i];
  27.             if(sum > rsum){
  28.                 rsum = sum;
  29.                 maxright = i;
  30.             }
  31.         }
  32.         list.add(maxleft);
  33.         list.add(maxright);
  34.         list.add(lsum+rsum);
  35.         return list;
  36.     }
  37.     // Function to recursively find the maximum sum subarray 
  38.     // in left and right subarrays
  39.     static List<Integer> maximumSumSubarray(int[] array, int low, int high){
  40.         List<Integer> list = new ArrayList<>();
  41.         if(low == high){
  42.             list.add(low);
  43.             list.add(high);
  44.             list.add(array[low]);
  45.             return list;
  46.         }
  47.         int mid = (low+high)/2;
  48.         List<Integer> output1 = maximumSumSubarray(array,low,mid);
  49.         List<Integer> output2 = maximumSumSubarray(array,mid+1,high);
  50.         List<Integer> output3 = maxCrossingSubarray(array,low,mid,high);
  51.         if(output1.get(2) >= output2.get(2) && output1.get(2) >= output3.get(2))
  52.             return output1;
  53.         else if (output2.get(2) >= output1.get(2) && 
  54.                  output2.get(2) >= output3.get(2))
  55.             return output2;
  56.         return output3;
  57.     }
  58.     // Function to read user-input and display the output
  59.     public static void main(String[] args) {
  60.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  61.         int size;
  62.         System.out.println("Enter the size of the array");
  63.         try {
  64.             size = Integer.parseInt(br.readLine());
  65.         } catch (Exception e) {
  66.             System.out.println("Invalid Input");
  67.             return;
  68.         }
  69.         int[] array = new int[size];
  70.         System.out.println("Enter array elements");
  71.         int i;
  72.         for (i = 0; i < array.length; i++) {
  73.             try {
  74.                 array[i] = Integer.parseInt(br.readLine());
  75.             } catch (Exception e) {
  76.                 System.out.println("An error Occurred");
  77.             }
  78.         }
  79.         List<Integer> output = maximumSumSubarray(array, 0, array.length-1);
  80.         System.out.println("The maximum sum subarray is");
  81.         int x = 0;
  82.         Iterator<Integer> it = output.getIterator();
  83.         for(Integer i : it){
  84.             System.out.print(i + " ");
  85.             x+=i;
  86.         }
  87.         System.out.println("nThe maximum sum is " + x);
  88.     }
  89. }
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
advertisement
 
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

Sanfoundry Global Education & Learning Series – Java Programs.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter