# Maximum Sum Circular Subarray
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-sum-circular-subarray)
Canonical: https://scaleengineer.com/dsa/problems/maximum-sum-circular-subarray
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Array, Queue, Monotonic Queue
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Two Sigma](https://scaleengineer.com/companies/two-sigma)
---
## Problem
Given a **circular integer array** `nums` of length `n`, return _the maximum possible sum of a non-empty **subarray** of_ `nums`.

A **circular array** means the end of the array connects to the beginning of the array. Formally, the next element of `nums[i]` is `nums[(i + 1) % n]` and the previous element of `nums[i]` is `nums[(i - 1 + n) % n]`.

A **subarray** may only include each element of the fixed buffer `nums` at most once. Formally, for a subarray `nums[i], nums[i + 1], ..., nums[j]`, there does not exist `i <= k1`, `k2 <= j` with `k1 % n == k2 % n`.

**Example 1:**

**Input:** nums = [1,-2,3,-2]
**Output:** 3
**Explanation:** Subarray [3] has maximum sum 3.

**Example 2:**

**Input:** nums = [5,-3,5]
**Output:** 10
**Explanation:** Subarray [5,5] has maximum sum 5 + 5 = 10.

**Example 3:**

**Input:** nums = [-3,-2,-3]
**Output:** -2
**Explanation:** Subarray [-2] has maximum sum -2.

**Constraints:**

* `n == nums.length`
* `1 <= n <= 3 * 104`
* `-3 * 104 <= nums[i] <= 3 * 104`

# Approaches
## Brute Force Approach
This approach exhaustively checks every possible contiguous subarray in the circular array. It iterates through all possible starting points and, for each starting point, considers all possible lengths from 1 up to the total number of elements `n`. By calculating the sum for each of these subarrays and keeping track of the maximum sum found, it guarantees finding the correct answer.
**Time:** O(n^2), where n is the length of the input array. The two nested loops result in a quadratic number of operations as we check every start position against every possible length. · **Space:** O(1), as we only use a constant amount of extra space for variables like `maxGlobalSum` and `currentSum`.
**Pros:** Simple to understand and implement.; It is a straightforward translation of the problem definition into code.
**Cons:** Highly inefficient for larger arrays due to its quadratic time complexity.; Likely to result in a 'Time Limit Exceeded' error on competitive programming platforms for typical constraints.
### Explanation
The brute-force method systematically explores all potential subarrays. A subarray in a circular context is defined by its starting position and its length. We can implement this with two nested loops.

- The outer loop iterates through each element of the array, `nums[i]`, treating it as the starting point of a potential maximum subarray.
- The inner loop then extends the subarray from this starting point, one element at a time. It calculates the sum of the current subarray and updates the overall maximum sum found so far.
- The circular nature of the array is handled by using the modulo operator (`%`) to calculate the indices of elements, which allows the subarray to 'wrap around' from the end of the array to the beginning.

```java
class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int maxGlobalSum = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = 0; j < n; j++) {
                int index = (i + j) % n;
                currentSum += nums[index];
                if (currentSum > maxGlobalSum) {
                    maxGlobalSum = currentSum;
                }
            }
        }
        return maxGlobalSum;
    }
}
```
### Algorithm
- Initialize `max_global_sum` with a very small number (or the first element).
- Use a nested loop structure. The outer loop `i` from `0` to `n-1` selects the starting element of the subarray.
- The inner loop `j` from `0` to `n-1` determines the length of the subarray (from 1 to n).
- Inside the inner loop, calculate the sum of the current subarray. To handle wrapping, use the modulo operator: `index = (i + j) % n`.
- Keep a `current_sum` for the subarray starting at `i` and extending for `j+1` elements.
- After calculating the sum of each possible subarray, compare it with `max_global_sum` and update if it's larger.
- After all loops complete, `max_global_sum` will hold the result.

## Kadane's Algorithm Variant
This optimal approach solves the problem in linear time by recognizing that the maximum sum subarray is either a standard one or one that wraps around. It uses Kadane's algorithm to find the maximum sum of a non-wrapping subarray. For the wrapping case, it calculates the total sum of the array and subtracts the minimum sum of a non-wrapping subarray (also found using a variant of Kadane's). The final answer is the larger of these two possibilities, with a special check for the edge case where all numbers are negative.
**Time:** O(n), where n is the number of elements in the array. The algorithm makes a single pass to compute all necessary values (total sum, max subarray sum, and min subarray sum). · **Space:** O(1), as it only requires a few variables to keep track of sums, regardless of the input array's size.
**Pros:** Extremely efficient with O(n) time complexity.; Solves the problem in a single pass through the array.; Elegantly combines two cases (wrapping and non-wrapping) for a complete solution.
**Cons:** The logic can be slightly non-intuitive at first, particularly the idea of inverting the problem to find the minimum subarray sum.; The edge case where all numbers are negative needs careful handling to avoid returning an incorrect result (0 for an empty subarray).
### Explanation
This efficient method is based on a clever observation. The subarray with the maximum sum can either be a contiguous block in the 'unrolled' array or a block that wraps around the ends.

1.  **Non-Wrapping Subarray:** We can find the maximum sum of any non-wrapping subarray using Kadane's algorithm. We iterate through the array, keeping track of the maximum sum ending at the current position and the overall maximum sum found so far.

2.  **Wrapping Subarray:** A subarray that wraps around is equivalent to the entire array minus a subarray from the middle. To maximize the sum of the wrapping part (`total_sum - middle_sum`), we must find the `middle_sum` that is as small as possible. Therefore, we need to find the minimum subarray sum. This can also be done in linear time with a simple modification to Kadane's algorithm (using `min` instead of `max`).

The potential maximum sum from a wrapping subarray is `total_sum - min_subarray_sum`.

Finally, we compare the results from both cases. However, we must handle the edge case where all elements are negative. In this scenario, the minimum subarray is the entire array, making `total_sum - min_subarray_sum = 0`. This represents an empty subarray, which is invalid. If the standard maximum subarray sum is negative, it means all numbers are non-positive, and this must be our answer.

```java
class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int totalSum = 0;
        int maxSum = nums[0];
        int currentMax = 0;
        int minSum = nums[0];
        int currentMin = 0;
        
        for (int num : nums) {
            // Standard Kadane's for maximum subarray sum
            currentMax = Math.max(currentMax + num, num);
            maxSum = Math.max(maxSum, currentMax);
            
            // Kadane's variant for minimum subarray sum
            currentMin = Math.min(currentMin + num, num);
            minSum = Math.min(minSum, currentMin);
            
            totalSum += num;
        }
        
        // If maxSum is positive, the answer is the max of non-wrapping sum (maxSum)
        // and wrapping sum (totalSum - minSum).
        // If maxSum is negative, it means all numbers are negative or zero.
        // In this case, totalSum - minSum would be 0 (as minSum == totalSum),
        // which corresponds to an empty subarray. So, we must return maxSum.
        if (maxSum > 0) {
            return Math.max(maxSum, totalSum - minSum);
        } else {
            return maxSum;
        }
    }
}
```
### Algorithm
- The maximum sum can be in one of two forms:
  1. A standard (non-wrapping) subarray.
  2. A wrapping subarray (prefix + suffix).
- **Case 1:** Find the maximum subarray sum for a non-wrapping array. This is a classic problem solved by **Kadane's Algorithm**. Let's call this `max_sum`.
- **Case 2:** The sum of a wrapping subarray is `total_array_sum - sum_of_the_middle_part`. To maximize this value, we need to find the subarray with the *minimum* sum and subtract it from the total. The minimum subarray sum can also be found using a variation of Kadane's algorithm. Let's call this `min_sum`.
- The maximum possible wrapping sum is `total_sum - min_sum`.
- **Combine Cases:** The answer is `max(max_sum, total_sum - min_sum)`.
- **Edge Case:** If all numbers are negative, `max_sum` will be the largest (least negative) number. `min_sum` will be equal to `total_sum`. In this situation, `total_sum - min_sum` would be 0, representing an empty subarray, which is not allowed. So, if `max_sum` is negative, the answer is simply `max_sum`. This can be checked by `if (max_sum > 0)`. If not, the wrapping case is invalid, and we return `max_sum`.

# Solutions
### Java

```java
class Solution {
public
  int maxSubarraySumCircular(int[] nums) {
    int s1 = nums[0], s2 = nums[0], f1 = nums[0], f2 = nums[0], total = nums[0];
    for (int i = 1; i < nums.length; ++i) {
      total += nums[i];
      f1 = nums[i] + Math.max(f1, 0);
      f2 = nums[i] + Math.min(f2, 0);
      s1 = Math.max(s1, f1);
      s2 = Math.min(s2, f2);
    }
    return s1 > 0 ? Math.max(s1, total - s2) : s1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxSubarraySumCircular(vector<int> &nums) {
    int s1 = nums[0], s2 = nums[0], f1 = nums[0], f2 = nums[0], total = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
      total += nums[i];
      f1 = nums[i] + max(f1, 0);
      f2 = nums[i] + min(f2, 0);
      s1 = max(s1, f1);
      s2 = min(s2, f2);
    }
    return s1 > 0 ? max(s1, total - s2) : s1;
  }
};

```

### Python

```python
class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int: s1 = s2 = f1 = f2 = nums[0] for num in nums[1:]: f1 = num + max(f1, 0) f2 = num + min(f2, 0) s1 = max(s1, f1) s2 = min(s2, f2) return s1 if s1 <= 0 else max(s1, sum(nums) - s2)

```