Asked: May 27, 20232023-05-27T09:34:57+00:00 2023-05-27T09:34:57+00:00In: Education

Smallest Sum Contiguous Subarray in Java

1 Answer

codemania

2023-05-27T09:35:36+00:00Added an answer on May 27, 2023 at 9:35 am

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.

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

Share
Share

You must login to add an answer.

Need An Account,

Point out the wrong statement. A. The standard instances are ...

Point out the correct statement. A. A volume is mounted ...

Which type of e‐commerce focuses on consumers dealing with ...

Misba Waqas

R.R.R SPORTS

Farhan Butt

Sign Up

Sign In

Forgot Password

Quearn Latest Questions

Smallest Sum Contiguous Subarray in Java

1 Answer

Related Questions