Maximum Sum Circular Subarray

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 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4

# Circular Array Maximum Sum

## Problem Description

Given a circular integer array `nums` of length `n`, the goal is to find the maximum possible sum of a non-empty subarray of `nums`. A circular array implies that the end connects to the beginning. Formally, the next element of `nums[i]` is `nums[(i + 1) % n]` and the previous element is `nums[(i - 1 + n) % n]`. A subarray may only include each element of the fixed buffer `nums` at most once.

**Examples:**

1.  `nums = [1, -2, 3, -2]`  =>  Output: `3` (Subarray `[3]`)
2.  `nums = [5, -3, 5]`  =>  Output: `10` (Subarray `[5, 5]`)
3.  `nums = [-3, -2, -3]` => Output: `-2` (Subarray `[-2]`)

## Naive Solution (Brute Force)

The simplest approach is to generate all possible subarrays and compute their sums, then find the maximum among them.  Since it's a circular array, we need to consider subarrays that wrap around.

```python
def max_subarray_circular_brute_force(nums):
    n = len(nums)
    max_sum = float('-inf')
    
    for i in range(n):
        for j in range(1, n + 1):
            current_sum = 0
            for k in range(j):
                index = (i + k) % n
                current_sum += nums[index]
            max_sum = max(max_sum, current_sum)
            
    return max_sum

Explanation:

This brute-force method iterates through every possible starting index i and every possible length j for the subarray. It computes the sum of each subarray and updates max_sum accordingly.

Optimal Solution (Kadane's Algorithm)

A more efficient solution can be derived using Kadane's Algorithm, which solves the maximum subarray sum problem in linear time. The maximum circular subarray sum can be found by considering two cases:

1. The maximum subarray is a regular subarray (not wrapping around).
2. The maximum subarray wraps around.

For the wrapping case, the maximum sum can be found by taking the total sum of the array and subtracting the minimum subarray sum (which is the part that's not in the wrapping subarray).

def max_subarray_circular(nums):
    n = len(nums)
    
    # Case 1: Max subarray is a regular subarray
    max_kadane = kadane(nums)
    
    # Case 2: Max subarray wraps around
    total_sum = sum(nums)
    inverted_nums = [-x for x in nums]
    max_wrap = total_sum + kadane(inverted_nums)
    
    # If all elements are negative, max_wrap will be 0, which is incorrect.
    # In this case, we return the max element (which is the least negative).
    if max_wrap == 0 and all(x <= 0 for x in nums):
        return max(nums)

    return max(max_kadane, max_wrap)

def kadane(nums):
    max_so_far = float('-inf')
    current_max = 0
    
    for x in nums:
        current_max = max(x, current_max + x)
        max_so_far = max(max_so_far, current_max)
        
    return max_so_far

Explanation:

1. kadane(nums): Standard Kadane's Algorithm to find the maximum subarray sum in a linear array.
2. max_kadane: The maximum subarray sum in the original array using Kadane's algorithm.
3. total_sum: The total sum of all elements in the array.
4. inverted_nums: Array with each element negated.
5. max_wrap: The maximum wraparound subarray sum, computed as total_sum + kadane(inverted_nums). This is because finding the minimum subarray sum (using inverted numbers and Kadane's) allows us to calculate the maximum wraparound sum: total_sum - min_subarray_sum.
6. The function returns the larger of max_kadane and max_wrap.

Big(O) Time Complexity Analysis

The optimal solution has a time complexity of O(n).

• kadane(nums) is O(n).
• Calculating total_sum is O(n).
• Inverting the array inverted_nums is O(n).
• The rest of the operations are constant time.

Therefore, the dominant factor is O(n).

Big(O) Space Complexity Analysis

The space complexity is O(n) due to the creation of the inverted_nums array. The Kadane's algorithm itself uses constant space, but in the circular array implementation, we create a new array of size n to store the inverted numbers. However, we can optimize the space to O(1) by inverting the numbers in-place and reverting them back after the kadane call.

Edge Cases

1. All negative numbers: If all numbers in the array are negative, the algorithm should return the least negative number (i.e., the maximum element).
2. All positive numbers: If all numbers are positive, the maximum subarray sum is simply the sum of all elements.
3. Empty array: Although the problem statement indicates n >= 1, handling an empty array is a good practice in real-world scenarios. In this case, return 0 or raise an exception, depending on the requirements.
4. Array with a single element: The algorithm should correctly handle an array with only one element, returning that element as the maximum sum.