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:

1 <= n <= 3 * 10^4 -3 * 10^4 <= nums[i] <= 3 * 10^4

## Circular Array Maximum Sum

This problem asks us to find the maximum possible sum of a non-empty subarray in a circular integer array. A circular array means the end connects to the beginning. The key constraint is that a subarray can include each element at most once.

### 1. Brute Force Solution

A naive approach would be to consider all possible subarrays and calculate their sums, keeping track of the maximum sum encountered. This would involve iterating through all possible start and end indices, making sure not to include any element more than once in the circular fashion.

```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
            subarray = []
            for k in range(j):
                index = (i + k) % n
                if index in subarray:
                    break
                subarray.append(index)
                current_sum += nums[index]
            if subarray:
                max_sum = max(max_sum, current_sum)
    return max_sum

This brute-force solution has a time complexity of O(n^3) because of the three nested loops, making it inefficient for large arrays.

2. Optimal Solution

A more efficient approach combines Kadane's Algorithm with some clever thinking about circular arrays.

The maximum subarray sum can either be:

1. A regular subarray (not wrapping around).
2. A subarray that wraps around.

For the first case, we can use Kadane's Algorithm to find the maximum subarray sum in linear time. For the second case, we can find the minimum subarray sum using a modified Kadane's Algorithm and subtract it from the total sum of the array. The maximum of these two cases will be our answer.

Here's the Python code:

def max_subarray_circular(nums):
    n = len(nums)
    total_sum = sum(nums)

    # Case 1: Max subarray sum without wrapping
    max_kadane = kadane(nums)

    # Case 2: Max subarray sum with wrapping
    min_kadane_arr = [-x for x in nums] #Invert to find minimum subarray
    max_wrap = total_sum + kadane(min_kadane_arr)

    # If all numbers are negative, kadane will return 0.  max_wrap will be 0 too
    # In that case, return the actual max
    if max_wrap == 0:
        return max_kadane
    
    return max(max_kadane, max_wrap)


def kadane(nums):
    max_so_far = float('-inf')
    current_max = 0

    for num in nums:
        current_max = max(num, current_max + num)
        max_so_far = max(max_so_far, current_max)
    
    return max_so_far

3. Big(O) Run-time Analysis

• Kadane's Algorithm: The kadane function iterates through the array once, resulting in O(n) time complexity.
• max_subarray_circular: It calls kadane twice and iterates once to compute the total sum. Therefore, the overall time complexity is O(n).

4. Big(O) Space Usage Analysis

• Kadane's Algorithm: Uses only constant extra space for max_so_far and current_max, resulting in O(1) space complexity.
• max_subarray_circular: Uses constant extra space, resulting in O(1) space complexity.

5. Edge Cases

• All Negative Numbers: If the array contains all negative numbers, the max_kadane will return the largest negative number (least negative). If all numbers are negative, max_wrap will be zero and kadane also could return zero. We need to avoid returning 0 if all nums are negative.
• All Positive Numbers: If the array contains all positive numbers, the maximum subarray sum will be the sum of all elements in the array, regardless of wrapping.
• Empty Array: The problem states the array must be non-empty. If it were empty, we'd need to handle this case separately.

def max_subarray_circular_edge_cases(nums):
    n = len(nums)
    if n == 0:
        return 0  # Or raise an exception

    total_sum = sum(nums)

    max_kadane = kadane(nums)
    min_kadane_arr = [-x for x in nums]
    max_wrap = total_sum + kadane(min_kadane_arr)

    #Edge case handling to account for all negative nums
    if max_wrap == 0 and max_kadane <= 0:
        return max(nums)

    return max(max_kadane, max_wrap)

This robust implementation handles edge cases gracefully and efficiently.