Smallest Sum Contiguous Subarray in Java

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

Problem Description

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

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

Output
Subarray = [-2 1 -3]

Sum = -4

Problem Solution
advertisement
advertisement

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

Program/Source Code

Here is the source code of the Java Program to Find the Minimum 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.

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

1. In function minCrossingSubarray(), the variables lsum and rsum are initialized to Integer.MAX_VALUE.
2. The loop for(i=mid;i>=0; i–) is used to find the minimum sum subarray when moving from the middle element towards the leftmost element.
3. The loop for(i=mid+1;i<=high; i++) is used to find the minimum sum subarray when moving from the middle element towards the rightmost element.
4. Finally, the output array is updated to contain the index of the leftmost and rightmost element, upto where the sum is maximum and the maximum sum is also stored in it as (lsum + rsum).
5. In function minimumSumSubarray(), the condition if(low == high) checks if there is only element, in the array.
6. If there is only one element, then the output array is updated as required.
7. Otherwise, the index of the middle element is calculated and the function minimumSumSubarray() is recursively called on left and right halves.
8. Finally, the function minCrossingSubarray() is called and the output arrays returned from the three calls are compared. The array containing the minimum sum is returned.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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 minimum sum subarray is
-2 1 -3 
The minimum sum is -4 
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
7
Enter array elements
7
6
5
1
2
3
4
The minimum sum subarray is
1 
The minimum sum is 1

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.