Max Subarray Sum in Circular Array Solution
Q: Write a function to find the maximum sum of a subarray in a circular array. What is the time complexity of your solution?
- Data Structures And Algorithms
- Senior level question
Explore all the latest Data Structures And Algorithms interview questions and answers
ExploreMost Recent & up-to date
100% Actual interview focused
Create Data Structures And Algorithms interview for FREE!
To find the maximum sum of a subarray in a circular array, we can use the following approach combining Kadane's algorithm with some adjustments for the circular nature of the array.
1. Use Kadane’s algorithm to find the maximum sum subarray for non-circular cases.
2. To handle the circular case, we:
- Calculate the total sum of the array.
- Invert the elements of the array (multiply by -1) and apply Kadane’s algorithm again to find the minimum sum subarray.
- The maximum sum circular subarray will then be the total sum of the array minus the minimum sum subarray found in the previous step.
3. The maximum sum will be the greater of the two values we computed above:
- The maximum sum of a non-circular subarray.
- The total array sum minus the minimum sum of the subarray (which is the maximum circular subarray).
### Implementation in Python:
```python
def max_circular_subarray_sum(arr):
def kadane(subarray):
max_sum = float('-inf')
current_sum = 0
for num in subarray:
current_sum += num
if current_sum > max_sum:
max_sum = current_sum
if current_sum < 0:
current_sum = 0
return max_sum
max_kadane = kadane(arr) # Maximum subarray sum without wrapping
total_sum = sum(arr) # Total sum of the array
inverted_array = [-x for x in arr] # Invert the array
max_inverted_kadane = kadane(inverted_array) # Largest negative subarray sum (smallest subarray sum)
max_circular = total_sum + max_inverted_kadane # Total sum - min subarray sum
if max_circular == 0: # Case when all numbers are negative
return max_kadane
return max(max_kadane, max_circular)
# Example usage
arr = [8, -1, 3, 4]
print(max_circular_subarray_sum(arr)) # Outputs: 15
```
### Time Complexity:
- The time complexity of this solution is O(N), where N is the number of elements in the array. This is because we perform Kadane's algorithm twice (once on the original array and once on the inverted).
### Clarification:
- This approach works effectively for arrays that may contain both positive and negative numbers. If all elements are negative, the algorithm correctly returns the maximum (least negative) single element, as the circular aspect in that case will not yield a beneficial result.
1. Use Kadane’s algorithm to find the maximum sum subarray for non-circular cases.
2. To handle the circular case, we:
- Calculate the total sum of the array.
- Invert the elements of the array (multiply by -1) and apply Kadane’s algorithm again to find the minimum sum subarray.
- The maximum sum circular subarray will then be the total sum of the array minus the minimum sum subarray found in the previous step.
3. The maximum sum will be the greater of the two values we computed above:
- The maximum sum of a non-circular subarray.
- The total array sum minus the minimum sum of the subarray (which is the maximum circular subarray).
### Implementation in Python:
```python
def max_circular_subarray_sum(arr):
def kadane(subarray):
max_sum = float('-inf')
current_sum = 0
for num in subarray:
current_sum += num
if current_sum > max_sum:
max_sum = current_sum
if current_sum < 0:
current_sum = 0
return max_sum
max_kadane = kadane(arr) # Maximum subarray sum without wrapping
total_sum = sum(arr) # Total sum of the array
inverted_array = [-x for x in arr] # Invert the array
max_inverted_kadane = kadane(inverted_array) # Largest negative subarray sum (smallest subarray sum)
max_circular = total_sum + max_inverted_kadane # Total sum - min subarray sum
if max_circular == 0: # Case when all numbers are negative
return max_kadane
return max(max_kadane, max_circular)
# Example usage
arr = [8, -1, 3, 4]
print(max_circular_subarray_sum(arr)) # Outputs: 15
```
### Time Complexity:
- The time complexity of this solution is O(N), where N is the number of elements in the array. This is because we perform Kadane's algorithm twice (once on the original array and once on the inverted).
### Clarification:
- This approach works effectively for arrays that may contain both positive and negative numbers. If all elements are negative, the algorithm correctly returns the maximum (least negative) single element, as the circular aspect in that case will not yield a beneficial result.