Kadane's Algorithm variation for circular arrays.
(arr)
| 9 | return max_so_far |
| 10 | |
| 11 | def max_circular_subarray(arr): |
| 12 | """Kadane's Algorithm variation for circular arrays.""" |
| 13 | max_kadane = kadanes_algorithm(arr) |
| 14 | |
| 15 | # Compute total array sum |
| 16 | total_sum = sum(arr) |
| 17 | |
| 18 | # Invert the array elements |
| 19 | inverted_arr = [-x for x in arr] |
| 20 | |
| 21 | # Find the maximum sum of the inverted array (minimum subarray sum) |
| 22 | max_inverted_kadane = kadanes_algorithm(inverted_arr) |
| 23 | |
| 24 | # The maximum circular sum is total_sum + max_inverted_kadane |
| 25 | # If max_inverted_kadane is equal to total_sum, it means all elements are negative |
| 26 | max_circular = total_sum + max_inverted_kadane if max_inverted_kadane != -total_sum else max_kadane |
| 27 | |
| 28 | return max(max_kadane, max_circular) |
| 29 | |
| 30 | # Example usage |
| 31 | arr = [1, -2, 4, -3] |
no test coverage detected