Problem Statement

You are given a circular integer array nums of length n.

• A circular array means the end of the array connects to the beginning.
• A subarray may wrap around.

Return the maximum possible sum of a non-empty subarray of nums.

Example 1:

Input: nums = [1,-2,3,-2]
Output: 3
Explanation: Maximum subarray is [3]

Example 2:

Input: nums = [5,-3,5]
Output: 10
Explanation: Maximum subarray is [5,5] (circular)

---

Approach to Solve the Problem (Simple Language)

Idea:

• This problem is an extension of Kadane’s Algorithm for maximum subarray sum.
• There are two cases for the maximum sum subarray:

1. Non-circular subarray (standard Kadane’s):
   • Maximum subarray does not wrap around
2. Circular subarray:
   • Maximum subarray wraps around
   • Formula: maxCircular = totalSum - minSubarraySum
     • Where totalSum is the sum of all elements
     • minSubarraySum is the minimum subarray sum (non-circular)

Steps:

1. Use Kadane’s Algorithm to find maxKadane (maximum sum subarray, non-circular).
2. Use modified Kadane to find minKadane (minimum sum subarray).
3. Calculate totalSum of the array.
4. If maxKadane < 0 → all numbers are negative → return maxKadane.
5. Else → return Math.max(maxKadane, totalSum - minKadane)

Why it works:

• Wrapping around is equivalent to excluding the minimum sum subarray in the middle.
• totalSum - minSubarraySum gives sum of remaining elements → maximum circular sum.

---

Java Code Solution

public class MaxSumCircularSubarray {

    public static int maxSubarraySumCircular(int[] nums) {
        int totalSum = 0;
        int maxSum = nums[0], curMax = 0;
        int minSum = nums[0], curMin = 0;

        for (int num : nums) {
            // Maximum subarray sum (Kadane's)
            curMax = Math.max(num, curMax + num);
            maxSum = Math.max(maxSum, curMax);

            // Minimum subarray sum
            curMin = Math.min(num, curMin + num);
            minSum = Math.min(minSum, curMin);

            totalSum += num;
        }

        if (maxSum < 0) {
            // All numbers are negative
            return maxSum;
        }

        // Maximum of non-circular and circular sum
        return Math.max(maxSum, totalSum - minSum);
    }

    public static void main(String[] args) {
        int[] nums = {5,-3,5};
        int result = maxSubarraySumCircular(nums);
        System.out.println("Maximum circular subarray sum: " + result); // Output: 10
    }
}

---

Dry Run Example

Input:

nums = [5,-3,5]

Step-by-step Execution:

1. Initialize:

totalSum=0, maxSum=5, curMax=0, minSum=5, curMin=0

2. Traverse array:

• num=5:
  • curMax = max(5, 0+5)=5 → maxSum=5
  • curMin = min(5, 0+5)=5 → minSum=5
  • totalSum=5
• num=-3:
  • curMax = max(-3, 5-3)=2 → maxSum=5
  • curMin = min(-3, 5-3)=-3 → minSum=-3
  • totalSum=2
• num=5:
  • curMax = max(5, 2+5)=7 → maxSum=7
  • curMin = min(5, -3+5)=2 → minSum=-3
  • totalSum=7

3. Compute circular max:

totalSum - minSum = 7 - (-3) = 10

4. Compare non-circular maxSum=7 vs circular=10 → return 10

Result: 10

---

Textual Diagram for Understanding

Array: [5, -3, 5]

Non-circular max subarray: [5] + [-3] + [5]?
- Kadane's max: 7 (subarray [5,-3,5])

Circular subarray:
- totalSum = 5 + (-3) + 5 = 7
- minSubarraySum = -3
- circularMax = totalSum - minSubarraySum = 7 - (-3) = 10

---

Complexity Analysis

• Time Complexity: O(n)
  • One pass to calculate max subarray, min subarray, and total sum.
• Space Complexity: O(1)
  • Only a few variables are used.

---

This approach efficiently handles both non-circular and circular maximum subarrays using a single-pass Kadane’s extension.