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

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.

```
 
```

//Java Program to Find the Minimum Sum in a Contiguous Sub-Array

```
 
```
```
import java.io.BufferedReader;
```
```
import java.io.InputStreamReader;
```
```
 
```
```
public class MinSumSubarray {
```

    // Function to find the crossing subarray with minimum sum

    static int[] minCrossingSubarray(int[] array, int low, int mid, int high){

```
        int lsum,rsum;
```

        lsum = rsum = Integer.MAX_VALUE;

```
        int sum = 0;
```
```
        int[] output = new int[3];
```
```
        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;
```
```
            }
```
```
        }
```
```
        output[0] = maxleft;
```
```
        output[1] = maxright;
```
```
        output[2] = lsum+rsum;
```
```
        return output;
```
```
    }
```

    // Function to recursively find minimum subarray in left and right parts

    static int[] minimumSumSubarray(int[] array, int low, int high){

```
        int[] output = new int[3];
```
```
        if(low == high){
```
```
            output[0] = low;
```
```
            output[1] = high;
```
```
            output[2] = array[low];
```
```
            return output;
```
```
        }
```
```
        int mid = (low+high)/2;
```

        int[] output1 = minimumSumSubarray(array,low,mid);

        int[] output2 = minimumSumSubarray(array,mid+1,high);

        int[] output3 = minCrossingSubarray(array,low,mid,high);

        if(output1[2] <= output2[2] && output1[2] <= output3[2])

```
            return output1;
```

        else if (output2[2] <= output1[2] && output2[2] <= output3[2])

```
            return output2;
```
```
        return output3;
```
```
    }
```
```
    // Fumction to read user input
```

    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");

```
            }
```
```
        }
```

        int[] output = minimumSumSubarray(array, 0, array.length-1);

        System.out.println("The minimum sum subarray is");

```
        int x = 0;
```

        for(i=output[0]; i<=output[1];i++){

            System.out.print(array[i] + " ");

```
            x+=array[i];
```
```
        }
```

        System.out.println("\nThe minimum sum is " + x);

```
    }
```
```
}
```

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.

« Prev - Java Program to Find the Column with Maximum Number of 1s

» Next - Java Program to Remove Duplicate Elements from Array

Related Posts:

Recommended Articles: