1public class Solution {
2    public int maxSubarraySumCircular(int[] A) {
3        int sumAll = 0;
4        
5        // Calculate total sum of the array
6        for (int a : A) {
7            sumAll += a;
8        }
9        
10        // Standard Kadane's Algorithm for the maximum subarray sum
11        int currentMax = A[0], maxSoFar = A[0];
12        for (int i = 1; i < A.length; i++) {
13            currentMax = Math.max(A[i], currentMax + A[i]);
14            maxSoFar = Math.max(maxSoFar, currentMax);
15        }
16        
17        // Modified Kadane's to find minimum so far
18        int currentMin = A[0], minSoFar = A[0];
19        for (int i = 1; i < A.length; i++) {
20            currentMin = Math.min(A[i], currentMin + A[i]);
21            minSoFar = Math.min(minSoFar, currentMin);
22        }
23
24        int max_circular = sumAll - minSoFar;
25        
26        return max_circular == 0 ? maxSoFar : Math.max(maxSoFar, max_circular);
27    }
28}

1#