Maximum Circular Subarray Sum

This program finds maximum circular subarray sum.

Problem Statement

Write a Java program to find maximum circular subarray sum in an integer array.

Source Code

1 public class MaxCircularSubarraySum {
2 public static void main(String[] args) {
3 System.out.println("Eduinq Maximum Circular Subarray Sum");
4 int[] arr = {8,-1,3,4};
5 int maxNormal=kadane(arr);
6 int total=0;
7 for(int num:arr) total+=num;
8 for(int i=0;i<arr.length;i++) arr[i]=-arr[i];
9 int maxCircular=total+kadane(arr);
10 System.out.println("Maximum circular subarray sum = "+Math.max(maxNormal,maxCircular));
11 }
12 static int kadane(int[] arr){
13 int maxSoFar=arr[0], maxEndingHere=arr[0];
14 for(int i=1;i<arr.length;i++){
15 maxEndingHere=Math.max(arr[i],maxEndingHere+arr[i]);
16 maxSoFar=Math.max(maxSoFar,maxEndingHere);
17 }
18 return maxSoFar;
19 }
20 }

Program Output

Eduinq Maximum Circular Subarray Sum
Maximum circular subarray sum = 15

Explanation

Kadanes algorithm finds normal max subarray. - Circular case handled by inverting array. - Total sum + inverted Kadane gives circular max. - Together finds maximum circular subarray sum. Conclusion: Shows how to extend Kadanes algorithm for circular arrays.

Quick Links to Explore