Maximum Sum Circular Subarray

• A subarray in a circular array is either non-wrapping or wrapping (suffix + prefix).
• Non-wrapping: found by standard max Kadane.
• Wrapping: equals the total minus the minimum subarray (remove the worst middle).
• Answer: max(maxKadane, total - minKadane).
• All-negative guard: if maxKadane < 0, return maxKadane (the least-negative element).
• Compute all three values in one pass: O(N) time, O(1) space.

What is the Maximum Sum Circular Subarray problem?

Given a circular array of integers where the last element wraps around to the first, find the maximum sum of any contiguous non-empty subarray. The subarray may wrap from the end back to the beginning. This is LeetCode 918.

For example, given [5, -3, 5], the best non-wrapping sum is 5, but wrapping [5, 5] (skipping -3 in the middle) gives 7.

How does the wrapping case reduce to min Kadane?

A subarray in a circular array has one of two shapes.

1. Non-wrapping: an ordinary contiguous subarray. Max Kadane finds the best.
2. Wrapping: a suffix joined to a prefix. This is the whole array minus a contiguous non-wrapping middle. To maximize the wrapping sum, remove the middle with the smallest sum.

So: bestWrapping = total - minKadane.

package com.bank.service;

public class MaxCircularSubarrayService {

    /**
     * Finds the best continuous P&L stretch in a circular weekly cycle.
     * Used by the National Bank of India treasury desk.
     */
    public static long maxCircularSum(long[] cashFlows) {
        long maxCur = cashFlows[0], maxGlobal = cashFlows[0];
        long minCur = cashFlows[0], minGlobal = cashFlows[0];
        long total = cashFlows[0];

        for (int i = 1; i < cashFlows.length; i++) {
            long val = cashFlows[i];
            total += val;

            // Max Kadane
            maxCur = Math.max(val, maxCur + val);
            maxGlobal = Math.max(maxGlobal, maxCur);

            // Min Kadane
            minCur = Math.min(val, minCur + val);
            minGlobal = Math.min(minGlobal, minCur);
        }

        // All-negative guard
        if (maxGlobal < 0) {
            return maxGlobal; // Least-negative element
        }
        return Math.max(maxGlobal, total - minGlobal);
    }

    public static void main(String[] args) {
        long[] flows = {50000, -30000, 50000, -10000, 20000};
        System.out.println("Best circular stretch: Rs."
            + maxCircularSum(flows));
    }
}

javac -d out com/bank/service/MaxCircularSubarrayService.java
java -cp out com.bank.service.MaxCircularSubarrayService

Best circular stretch: Rs.110000

Why is the all-negative guard necessary?

If every element is negative, then minGlobal equals the total (the entire array is the minimum subarray), so total - minGlobal becomes zero. But zero corresponds to an empty subarray, which violates the non-empty requirement. We detect this by checking maxGlobal < 0, which happens exactly when all elements are negative, and return maxGlobal directly (the least-negative single element).

// All-negative example: [-5, -3, -1]
// maxGlobal = -1, minGlobal = -9, total = -9
// total - minGlobal = -9 - (-9) = 0 <- WRONG (empty subarray)
// Guard: maxGlobal < 0, so return -1

How do you compute all three values in one pass?

You run max Kadane, min Kadane, and a running total simultaneously in the same loop. Each uses its own pair of variables. This keeps the algorithm to a single linear pass with O(1) space.

What are the edge cases?

Several edge cases require attention.

• All negative: guard returns the least-negative element.
• All positive: the entire array is both the max subarray and the result. Wrapping would remove nothing.
• Single element: the answer is that element.
• Wrapping gives better result: when the worst middle is large and negative, wrapping wins.

package com.bank.core;

public class CircularEdgeCases {
    public static void main(String[] args) {
        System.out.println(maxCirc(new long[]{-5, -3, -1}));      // -1
        System.out.println(maxCirc(new long[]{1, 2, 3, 4}));      // 10
        System.out.println(maxCirc(new long[]{42}));               // 42
        System.out.println(maxCirc(new long[]{8, -8, 9, -9, 10}));// 19
    }

    static long maxCirc(long[] arr) {
        long maxC = arr[0], maxG = arr[0], minC = arr[0], minG = arr[0], total = arr[0];
        for (int i = 1; i < arr.length; i++) {
            total += arr[i];
            maxC = Math.max(arr[i], maxC + arr[i]); maxG = Math.max(maxG, maxC);
            minC = Math.min(arr[i], minC + arr[i]); minG = Math.min(minG, minC);
        }
        return maxG < 0 ? maxG : Math.max(maxG, total - minG);
    }
}

-1
10
42
19

What is the time and space complexity?

Time is O(N): one pass computing three values simultaneously. Space is O(1): a handful of scalar variables. This is optimal.

How is this related to max and min Kadane?

This problem combines three concepts: max Kadane (non-wrapping case), min Kadane (identifies the worst middle to remove), and the total sum (wrapping case is total minus minimum). It is the synthesis of the Kadane family.

| Component | Purpose |
|---|---|
| Max Kadane | Best non-wrapping subarray |
| Min Kadane | Worst middle segment to remove for wrapping |
| Total sum | Full array sum, needed for the wrapping formula |
| All-negative guard | Prevents returning zero for an empty subarray |

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• The removal reframing: wrapping = total - worst middle. This reframing is the key insight many candidates miss.
• The all-negative guard is not optional: it is the single detail that separates correct from wrong.
• Alternative approach: duplicate the array (concatenate it with itself) and run a constrained max Kadane with a window of length N. This is O(N) but uses O(N) space, which is worse.
• Monetary overflow: accumulate total and running sums in long for large financial batches.