Naive Solution

The brute force approach would be to iterate through all possible subarrays and calculate their sums. For a circular array, this involves considering subarrays that wrap around from the end to the beginning. This approach is highly inefficient.

Code (Python)

def max_subarray_sum_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

Big O Analysis

• Time Complexity: O(n^2), due to the nested loops.
• Space Complexity: O(1), as we are only using a constant amount of extra space.

Optimal Solution

The optimal solution involves using Kadane's Algorithm to find the maximum subarray sum and then considering the case where the maximum subarray wraps around. The maximum sum in a circular array can be one of two things:

1. The maximum subarray sum in the regular array.
2. The total sum of the array minus the minimum subarray sum.

We use Kadane's algorithm to find both the maximum and minimum subarray sums. The maximum circular subarray sum will be the larger of the maximum subarray sum and the total sum minus the minimum subarray sum. We also handle the case where all numbers are negative, which would result in a total sum equal to the minimum sum. In that case, we simply return the maximum element of the original array.

Code (Python)

def max_subarray_sum_circular(nums):
    n = len(nums)
    max_kadane = kadane(nums)

    total_sum = sum(nums)
    inverted_nums = [-num for num in nums]
    max_circular = total_sum + kadane(inverted_nums)

    if max_circular == 0: # handles edge case, when all numbers are negative
         return max_kadane

    return max(max_kadane, max_circular)


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

Big O Analysis

• Time Complexity: O(n), as we iterate through the array a constant number of times.
• Space Complexity: O(1), as we are only using a constant amount of extra space.

Edge Cases

• Empty array: The problem statement says 1 <= n <= 3 * 10^4 so we don't need to worry about an empty array
• All negative numbers: If all numbers are negative, the maximum subarray sum will be the largest negative number (least negative). Kadane's algorithm will handle this.
• All positive numbers: If all numbers are positive, the maximum subarray sum will be the sum of all numbers.
• Mixed positive and negative numbers: Kadane's algorithm handles this case correctly.