To solve this problem, we need to find the maximum sum of a non-empty subarray in a circular array. A circular array means the end of the array connects back to the start, so the subarray can wrap around from the end to the beginning.

Approach

The solution involves two main cases for the maximum subarray sum:

1. Non-wrapping Subarray: This is the standard maximum subarray sum found using Kadane's algorithm.
2. Wrapping Subarray: This subarray includes elements from the end of the array and the beginning. To compute this, we use the total sum of the array minus the minimum subarray sum (found using a modified Kadane's algorithm for minimum sum).

Key Insight: The wrapping subarray sum is the total sum of the array minus the minimum subarray sum (since the minimum subarray is in the middle, the elements outside it form the wrapping subarray).

Edge Case: If all elements are negative, the maximum subarray sum is the largest element (since the wrapping sum would be zero, which is not valid for a non-empty subarray).

Solution Code

def kadane_max(arr):
    current_max = global_max = arr[0]
    for num in arr[1:]:
        current_max = max(num, current_max + num)
        global_max = max(global_max, current_max)
    return global_max

def kadane_min(arr):
    current_min = global_min = arr[0]
    for num in arr[1:]:
        current_min = min(num, current_min + num)
        global_min = min(global_min, current_min)
    return global_min

def max_circular_subarray_sum(arr):
    max_k = kadane_max(arr)
    min_k = kadane_min(arr)
    total = sum(arr)

    if total == min_k:
        return max_k
    else:
        return max(max_k, total - min_k)

Explanation

1. Kadane's Algorithm for Maximum Sum: This algorithm finds the maximum sum of a contiguous subarray by keeping track of the current maximum sum ending at each position and updating the global maximum sum.
2. Modified Kadane's Algorithm for Minimum Sum: This is similar to the maximum sum algorithm but tracks the minimum sum of a contiguous subarray.
3. Total Sum Calculation: The total sum of the array helps in computing the wrapping subarray sum.
4. Edge Case Handling: If the total sum equals the minimum subarray sum (all elements are negative), the result is the maximum subarray sum (the largest element). Otherwise, the result is the maximum of the non-wrapping and wrapping subarray sums.

This approach ensures an optimal time complexity of O(n) (since each algorithm runs in linear time) and a space complexity of O(1) (using constant extra space). This makes it efficient for large input arrays.

作者声明:本文包含人工智能生成内容。