Find Maximum Circular Subarray Sum

Title: Find Maximum Circular Subarray Sum

In this guide, you’ll learn how to find the maximum sum of a contiguous subarray in a circular array, where the array wraps around so a subarray is allowed to start near the end and continue from the beginning. We’ll build on Kadane’s algorithm, extend it to cover the wrap-around case, and walk through a complete Java implementation with a full trace, worked examples, and the edge cases interviewers love to probe.

Understanding the Problem

A circular array behaves as if its last element is immediately followed by its first element again. Given such an array of integers, you need to return the maximum possible sum of a non-empty subarray, where the subarray may wrap from the end of the array back to the beginning.

For a plain array, Kadane’s algorithm already finds the maximum subarray sum in a single pass. The twist here is that the best subarray might straddle the array’s boundary, for example picking up the last two elements and the first element together. A brute-force fix would duplicate the array and re-run Kadane’s algorithm over a window capped at numbers.length, but that costs extra time and space we don’t need.

The key insight is that a wrapping subarray is exactly the complement of some normal, non-wrapping subarray. If you remove a contiguous middle chunk from the array, whatever is left on the two ends is effectively wrapped around. So the best wrapping sum equals totalSum minus the minimum contiguous subarray sum, found using a mirrored version of Kadane’s algorithm.

Approach and Algorithm Steps

1. Compute totalSum, the sum of every element in numbers.
2. Run Kadane’s algorithm for the maximum subarray sum (maxKadane), tracking currentMax and globalMax while scanning left to right.
3. Run a mirrored Kadane’s algorithm for the minimum subarray sum (minKadane), tracking currentMin and globalMin the same way, but keeping the smaller candidate at each step.
4. Compute the wrap candidate maxWrap as totalSum - minKadane; this represents the best subarray that wraps around the boundary.
5. If maxKadane is negative, every element is negative, so return maxKadane directly, since a wrapping subarray would wrongly include all or none of the elements.
6. Otherwise, return Math.max(maxKadane, maxWrap) as the maximum circular subarray sum.

Java Program

public class MaxCircularSubarraySum {

    public static int maxSubarraySumCircular(int[] numbers) {
        int maxKadane = kadaneMax(numbers);

        int totalSum = 0;
        for (int num : numbers) {
            totalSum += num;
        }

        int minKadane = kadaneMin(numbers);
        int maxWrap = totalSum - minKadane;

        if (maxKadane < 0) {
            return maxKadane;
        }

        return Math.max(maxKadane, maxWrap);
    }

    private static int kadaneMax(int[] numbers) {
        int currentMax = numbers[0];
        int globalMax = numbers[0];

        for (int i = 1; i < numbers.length; i++) {
            currentMax = Math.max(numbers[i], currentMax + numbers[i]);
            globalMax = Math.max(globalMax, currentMax);
        }

        return globalMax;
    }

    private static int kadaneMin(int[] numbers) {
        int currentMin = numbers[0];
        int globalMin = numbers[0];

        for (int i = 1; i < numbers.length; i++) {
            currentMin = Math.min(numbers[i], currentMin + numbers[i]);
            globalMin = Math.min(globalMin, currentMin);
        }

        return globalMin;
    }

    public static void main(String[] args) {
        int[] numbers = {8, -1, 3, 4};
        int result = maxSubarraySumCircular(numbers);
        System.out.println("Maximum circular subarray sum: " + result);
    }
}

Explanation of the Program

The method maxSubarraySumCircular orchestrates the whole algorithm. It computes totalSum, then delegates to two private helpers, kadaneMax and kadaneMin, each running the classic Kadane’s scan but optimizing for a different direction.

• kadaneMax tracks the best sum of a subarray ending at the current index in currentMax, resetting to numbers[i] whenever extending the previous subarray would make things worse.
• kadaneMin mirrors the same logic with Math.min, finding the lowest-sum contiguous subarray instead of the highest.
• maxWrap is derived rather than scanned directly: totalSum - minKadane gives the sum of whatever is left after removing the minimum-sum middle chunk, which is exactly the wrapped subarray.
• The if (maxKadane < 0) guard protects against the all-negative case, where minKadane would equal totalSum and maxWrap would incorrectly evaluate to 0.

Step-by-Step Trace

For the input numbers = {5, -3, 5}, the target output is 10, achieved by wrapping the last element around to the first. Here's how kadaneMax finds the non-wrapping half of that answer; currentMax and globalMax both start at numbers[0] = 5 before the loop begins.

At the end of iteration i, currentMax holds the maximum sum of a subarray ending at index i, and globalMax holds the best such sum seen so far, here finishing at maxKadane = 7.

Running the mirrored kadaneMin scan over the same input gives minKadane = -3 (the single element at index 1), so maxWrap = totalSum - minKadane = 7 - (-3) = 10. Since maxKadane is not negative, the final answer is Math.max(7, 10) = 10, the wrap-around sum of the two 5s.

Examples

Example 1: All Positive Elements

int[] numbers = {1, 2, 3, 4, 5};
// Expected output: 15 (no wrap needed; the whole array is the answer)
System.out.println(MaxCircularSubarraySum.maxSubarraySumCircular(numbers));

When every element is positive, the best subarray is always the entire array, so maxKadane already equals totalSum. maxWrap can never beat it here, because minKadane would have to be negative to help, which can't happen when every element is positive.

Example 2: All Negative Elements

int[] numbers = {-3, -2, -5};
// Expected output: -2 (the single least negative element)
System.out.println(MaxCircularSubarraySum.maxSubarraySumCircular(numbers));

Here maxKadane evaluates to -2, the best single element. Because it's negative, the method returns it directly instead of computing a meaningless maxWrap of 0.

Example 3: A True Wrap-Around Winner

int[] numbers = {8, -1, 3, 4};
// Expected output: 15 (wraps as 3 + 4 + 8, skipping the -1)
System.out.println(MaxCircularSubarraySum.maxSubarraySumCircular(numbers));

This is the case the wrap-around logic exists for. maxKadane only reaches 14 (the whole array), but excluding the single element -1 gives maxWrap = 15, so the circular subarray 3 + 4 + 8 wins.

Common Mistakes to Avoid

These are the mistakes that trip up most learners the first time they implement the circular variant of Kadane's algorithm.

• Returning 0 for arrays of all negative numbers - without the guard, minKadane equals totalSum on an all-negative array, so maxWrap collapses to 0, a sum no real subarray can produce. Always check maxKadane < 0 first.
• Reusing one Kadane scan for both max and min - sharing currentMax and currentMin between the two passes corrupts both results. Run two independent loops, each with its own pair of tracking variables.
• Treating maxWrap as the final answer - returning totalSum - minKadane directly, without comparing it against maxKadane, misses cases where the best subarray never wraps, such as {1, 2, 3, 4, 5}. Always take Math.max(maxKadane, maxWrap).
• Forgetting that minKadane can equal the whole array's sum - when every element is negative, the minimum subarray is the entire array, which is exactly why the all-negative guard is needed before trusting maxWrap.

Edge Cases to Test

Walk through these input shapes before calling the implementation done; interviewers watch for this habit.

• Single-element array
• All negative elements
• All positive elements
• Two-element array
• All elements identical
• Integer.MIN_VALUE / Integer.MAX_VALUE present
• Null array reference

Additional Considerations

Both Kadane passes run in a single left-to-right scan, so the overall time complexity is O(n). Space usage is O(1) beyond the input array, since only a handful of scalar variables are tracked.

If numbers can include values near Integer.MIN_VALUE or Integer.MAX_VALUE, totalSum and the running sums inside each Kadane pass can overflow a 32-bit int. Switching those accumulators to long removes that risk without changing the algorithm's logic.

Why Not Duplicate the Array?

A common alternative is to concatenate numbers with itself and run a sliding-window Kadane's scan capped at length numbers.length. That also solves the problem, but it doubles the memory footprint and iterates over up to 2n elements instead of n, so the two-pass approach above is the leaner choice.

Interview Follow-up Questions

Once you can explain the base solution, expect an interviewer to push further with questions like these.

• What if the array contains only one element? - the answer is that element itself; both Kadane passes trivially return it, so maxWrap can never exceed maxKadane.
• What if you need the actual indices of the winning circular subarray, not just the sum? - track start and end indices alongside currentMax and currentMin during each Kadane pass, then reconstruct the wrap range from the minimum subarray's complement.
• What if the array arrives as a stream too large to buffer twice? - you can maintain the running Kadane max and min online, but a correct circular evaluation needs the final totalSum, so you must know the stream's length in advance or buffer it once.
• What if element values could overflow a 32-bit int during summation? - accumulate totalSum and both Kadane passes using long instead of int so large magnitude inputs can't silently wrap around.

Conclusion

You've now seen how a circular subarray problem reduces to two ordinary Kadane's scans plus one careful guard for the all-negative case. The same trick, that the complement of the minimum subarray gives the best wrap, shows up anywhere a problem wraps around a boundary, so it's worth internalizing rather than memorizing.

Try adapting maxSubarraySumCircular to return the winning subarray's indices instead of just its sum, or to handle a circular array of doubles, to deepen your understanding. You can learn more about array-based algorithms in our Arrays category.