Java Program to Find Subarray Which Has the Largest Sum in a Given Circular Array of Integers

Java Program to Find Subarray Which Has the Largest Sum in a Given Circular Array of Integers

by

In the previous article, we have seen Java Program to Find Maximum Sum of Two Integers in an Array of Integers

In this article we are going to see how to find subarray which has the largest sum in a given circular array of integers in Java programming language.

Java Program to Find Subarray Which Has the Largest Sum in a Given Circular Array of Integers

There can two cases in this problem.

  1. NO wrapping: The subarray is present between the 1st and the last element of the array.
  2. Wrapping: If the subarray consists of some elements from the beginning and some from the end.
  • In case 1, usual Kadane’s algorithm will do the job.
  • In case 2, we have to modify the Kadane’s algorithm to find the min sum subarray and subtract it from the array sum to get the required max sum subarray with wrapping.

Since we don’t know beforehand, which case will occur, we’ll check for both the cases.

Approach:

  1. Create scanner class object.
  2. Ask use length of the array.
  3. Initialize the array with given size.
  4. Ask the user for array elements.
  5. Check if the array is empty, exit the program.
  6. Check if all the elements of the array are negative return the max value of the array.
  7. Obtain the max subarray for both case1 and case2.
  8. Print the max of those two.

Program:

import java.util.Arrays;
import java.util.Scanner;

public class Main 
{
    public static void main(String[] args) 
    {
        // create scanner class object
        Scanner sc = new Scanner(System.in);
        // take input from user for array size
        System.out.print("Enter the size of array: ");
        int n = sc.nextInt();
        // initialize array with size n
        int[] arr = new int[n];
        // take input from user for array elements
        System.out.print("Enter array elements: ");
        for (int i = 0; i < n; i++) 
        {
            arr[i] = sc.nextInt();
        }
        findMaxSubarray(arr);

    }

    public static void findMaxSubarray(int[] arr) 
    {
        // check if array is empty
        if (arr.length == 0) {
            System.out.println("Array is empty");
            return;
        }
        // check if array is negative
        boolean flag = true;
        for (int i : arr) 
        {
            if (i >= 0) 
            {
                flag = false;
                break;
            }
        }
        if (flag) 
        {
            System.out.println("The maximum subarray sum of circular array " + Arrays.toString(arr) + " is "
                    + Arrays.stream(arr).max().getAsInt());
           return;
       }
        // case 1
        int case1 = maxKadane(arr);
        // apply case 2
        int case2 = sum(arr) - minKadane(arr);

        if (case1 > case2)
            System.out.println("The maximum subarray sum of circular array " + Arrays.toString(arr) + " is " + case1);
        else
            System.out.println("The maximum subarray sum of circular array " + Arrays.toString(arr) + " is " + case2);

    }

    public static int sum(int[] arr) 
    {
        int sum = 0;
        for (int i : arr) 
        {
            sum += i;
        }
        return sum;
    }

    public static int maxKadane(int[] arr) 
    {
        int globalMax = Integer.MIN_VALUE;
        int currMax = 0;
        for (int i = 0; i < arr.length; i++) 
        {
            currMax = currMax + arr[i];
            // reset curmax if it is negative
            if (currMax < 0) {
                currMax = 0;
            }
            // update global max
            if (globalMax < currMax) 
            {
                globalMax = currMax;
            }
        }
        return globalMax;
    }

    public static int minKadane(int[] arr) 
    {
        int globalMin = Integer.MAX_VALUE;
        int currMin = 0;
        for (int i = 0; i < arr.length; i++) 
        {
            currMin = currMin + arr[i];
            // reset curmax if it is positive
            if (currMin > 0) {
                currMin = 0;
            }
            // update global max
            if (globalMin > currMin) 
            {
                globalMin = currMin;
            }
        }
        return globalMin;
    }
}

Output:

Enter the size of array: 5
Enter array elements: 4 2 8 1 3 
The maximum subarray sum of circular array [4, 2, 8, 1, 3] is 18

Have you mastered basic programming topics of java and looking forward to mastering advanced topics in a java programming language? Go with these ultimate Advanced java programs examples with output & achieve your goal in improving java coding skills.

Related Java Programs: