# LeetCode 918: Maximum Sum Circular Subarray

## Problem Restatement

We are given a circular integer array `nums`.

A circular array means the element after the last element is the first element again.

We need to find the maximum possible sum of a non-empty subarray.

A subarray may:

- Stay completely inside the array
- Or wrap around the end back to the beginning

Each element can only be used once.

The official problem statement defines circular subarrays this way. ([leetcode.com](https://leetcode.com/problems/maximum-sum-circular-subarray/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Maximum possible subarray sum |
| Circular rule | Subarray may wrap around |
| Constraint | Subarray must be non-empty |

Function shape:

```python
def maxSubarraySumCircular(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [1, -2, 3, -2]
```

Best subarray:

```python
[3]
```

Answer:

```python
3
```

Example 2:

```python
nums = [5, -3, 5]
```

The best subarray wraps around:

```python
[5] + [5]
```

Sum:

```python
10
```

Answer:

```python
10
```

Example 3:

```python
nums = [-3, -2, -3]
```

The best subarray is:

```python
[-2]
```

Answer:

```python
-2
```

## First Thought: Try Every Circular Subarray

A direct method is:

1. Choose every possible start index.
2. Extend the subarray around the circle.
3. Compute every possible sum.

This works, but there are too many subarrays.

The time complexity becomes quadratic.

We need a linear-time approach.

## Key Insight

There are two possible types of optimal subarrays.

### Case 1: Normal Subarray

The best subarray does not wrap around.

Then the problem becomes the classic maximum subarray problem solved by Kadane's algorithm.

Example:

```python
[1, -2, 3, -2]
```

Best normal subarray:

```python
[3]
```

### Case 2: Circular Subarray

The best subarray wraps around.

Example:

```python
[5, -3, 5]
```

The best circular subarray uses:

```python
last 5 + first 5
```

Instead of directly finding the wrapped subarray, think about what gets excluded.

The wrapped subarray equals:

```python
total_sum - middle_subarray
```

The excluded middle part should have the smallest possible sum.

So:

```python
best_circular = total_sum - minimum_subarray_sum
```

## Important Edge Case

Suppose all numbers are negative.

Example:

```python
[-3, -2, -3]
```

Then:

```python
minimum_subarray_sum = total_sum
```

So:

```python
total_sum - minimum_subarray_sum = 0
```

But `0` is invalid because the subarray must be non-empty.

In this situation, the correct answer is simply the maximum element, which Kadane already gives.

So:

- If the maximum normal subarray sum is negative, return it directly.
- Otherwise, return the larger of:
  - normal maximum
  - circular maximum

## Algorithm

1. Use Kadane's algorithm to find:
   - Maximum subarray sum
2. Use a modified Kadane's algorithm to find:
   - Minimum subarray sum
3. Compute:
   - `total_sum`
4. If the maximum subarray sum is negative:
   - Return it
5. Otherwise:
   - Return:

```python
max(max_subarray_sum, total_sum - min_subarray_sum)
```

## Kadane's Algorithm

Normal Kadane:

```python
current_max = max(num, current_max + num)
best_max = max(best_max, current_max)
```

Minimum version:

```python
current_min = min(num, current_min + num)
best_min = min(best_min, current_min)
```

## Correctness

Any optimal circular subarray belongs to one of two categories.

If it does not wrap around the array boundary, then it is a normal subarray. Kadane's algorithm correctly computes the maximum such sum.

If it wraps around, then the selected elements consist of a suffix and a prefix of the array. The elements not selected form one contiguous middle subarray.

Therefore:

```python
wrapped_sum = total_sum - excluded_middle_sum
```

To maximize the wrapped sum, we must minimize the excluded middle sum. The modified Kadane algorithm correctly computes the minimum subarray sum.

So the best wrapped subarray sum is:

```python
total_sum - min_subarray_sum
```

The algorithm compares the best normal subarray and the best wrapped subarray, so it considers every possible optimal solution.

If all numbers are negative, then the minimum subarray equals the entire array. Subtracting it from the total gives zero, which would represent an empty subarray and is invalid. In this case, the maximum normal subarray is the correct answer.

Therefore, the algorithm always returns the maximum valid circular subarray sum.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | The array is scanned once |
| Space | `O(1)` | Only a few variables are used |

## Implementation

```python
class Solution:
    def maxSubarraySumCircular(self, nums: list[int]) -> int:
        total_sum = 0

        current_max = 0
        best_max = nums[0]

        current_min = 0
        best_min = nums[0]

        for num in nums:
            total_sum += num

            current_max = max(num, current_max + num)
            best_max = max(best_max, current_max)

            current_min = min(num, current_min + num)
            best_min = min(best_min, current_min)

        if best_max < 0:
            return best_max

        return max(best_max, total_sum - best_min)
```

## Code Explanation

Track the total array sum:

```python
total_sum = 0
```

The maximum subarray logic is standard Kadane:

```python
current_max = max(num, current_max + num)
best_max = max(best_max, current_max)
```

`current_max` means:

```python
best subarray ending at current position
```

The minimum version works similarly:

```python
current_min = min(num, current_min + num)
best_min = min(best_min, current_min)
```

At the end:

```python
total_sum - best_min
```

gives the best wrapped subarray sum.

If all numbers are negative:

```python
if best_max < 0:
    return best_max
```

Otherwise compare both cases:

```python
return max(best_max, total_sum - best_min)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxSubarraySumCircular([1, -2, 3, -2]) == 3
    assert s.maxSubarraySumCircular([5, -3, 5]) == 10
    assert s.maxSubarraySumCircular([-3, -2, -3]) == -2
    assert s.maxSubarraySumCircular([3, -1, 2, -1]) == 4
    assert s.maxSubarraySumCircular([3, -2, 2, -3]) == 3
    assert s.maxSubarraySumCircular([2, 2, 2]) == 6
    assert s.maxSubarraySumCircular([-1]) == -1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, -2, 3, -2]` | Best subarray is normal |
| `[5, -3, 5]` | Best subarray wraps |
| All negative | Checks empty-subarray edge case |
| Mixed positive and negative | Standard Kadane behavior |
| Wrapped and non-wrapped compete | Ensures correct maximum chosen |
| All positive | Entire array is optimal |
| Single negative value | Minimum input |