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
Kadane's algorithm first finds the normal maximum subarray, and the circular case is handled by inverting the array and running Kadane's again, so total sum plus this inverted result gives the circular maximum, and the greater of the two cases is the answer.