---
Difficulty: Hard
Source: 160 Days of Problem Solving
Tags:
- Arrays
---
# š _Day 12. Max Circular Subarray Sum_ š§
The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/arrays-gfg-160/problem/max-circular-subarray-sum-1587115620)
## š” **Problem Description:**
Given an array of integers `arr[]` in a circular fashion, return the maximum sum of a subarray that can be obtained assuming the array is circular.
**Note:** The solution should account for both regular and circular subarrays.
## š **Example Walkthrough:**
**Input:**
`arr[] = [8, -8, 9, -9, 10, -11, 12]`
**Output:**
`22`
**Explanation:**
Starting from the last element of the array, i.e., `12`, and moving in a circular fashion, the maximum subarray is `[12, 8, -8, 9, -9, 10]`, which gives the maximum sum of `22`.
**Input:**
`arr[] = [10, -3, -4, 7, 6, 5, -4, -1]`
**Output:**
`23`
**Explanation:**
Maximum sum of the circular subarray is `23`. The subarray is `[7, 6, 5, -4, -1, 10]`.
### Constraints:
- $`1 <= arr.size() <= 10^5`$
- $`-10^4 <= arr[i] <= 10^4`$
## šÆ **My Approach:**
1. **Kadane's Algorithm for Maximum Subarray Sum:**
- First, use Kadaneās algorithm to find the maximum subarray sum in the non-circular array (normal subarray sum).
2. **Kadaneās Algorithm for Minimum Subarray Sum:**
- Use Kadaneās algorithm to find the minimum subarray sum in the array. This helps in calculating the circular maximum subarray sum.
3. **Total Sum Calculation:**
- Calculate the total sum of the array and subtract the minimum subarray sum from it. This will give us the maximum circular subarray sum.
4. **Final Answer:**
- The answer is the maximum of:
- The result from Kadaneās algorithm (non-circular subarray sum).
- The result from the circular subarray sum calculation (total sum - minimum subarray sum).
5. **Handle All Negative Case:**
- If the entire array consists of negative numbers, return the result from Kadaneās algorithm for the maximum subarray sum.
### _*or*_
1. **Kadaneās Algorithm**:
- The problem is split into two parts: finding the maximum sum of a normal subarray and finding the maximum sum of a circular subarray.
2. **Steps:**
- First, use Kadane's algorithm to find the maximum sum of a regular subarray.
- Then, calculate the total sum of the array and use Kadaneās algorithm again on the negated values of the array to find the minimum subarray sum.
- The circular subarray sum is obtained by subtracting the minimum subarray sum from the total sum.
- Return the maximum of the regular subarray sum and the circular subarray sum.
## š **Time and Auxiliary Space Complexity**
- **Expected Time Complexity:** O(n), where `n` is the size of the array. Kadane's algorithm runs in linear time, and we perform only two linear scans of the array.
- **Expected Auxiliary Space Complexity:** O(1), as we only use a constant amount of additional space.
## š **Solution Code**
## Code (C)
```c
int max(int a, int b) {
return a > b ? a : b;
}
int min(int a, int b) {
return a < b ? a : b;
}
int circularSubarraySum(int arr[], int n) {
int total_sum = 0, max_sum = INT_MIN, min_sum = INT_MAX;
int curr_max = 0, curr_min = 0;
int all_negative = 1;
for (int i = 0; i < n; i++) {
total_sum += arr[i];
curr_max = max(arr[i], curr_max + arr[i]);
max_sum = max(max_sum, curr_max);
curr_min = min(arr[i], curr_min + arr[i]);
min_sum = min(min_sum, curr_min);
if (arr[i] > 0) all_negative = 0;
}
if (all_negative) return max_sum;
return max(max_sum, total_sum - min_sum);
}
```
## Code (Cpp)
```cpp
class Solution {
public:
int circularSubarraySum(vector& a) {
int total_sum = 0, max_sum = INT_MIN, min_sum = INT_MAX;
int curr_max = 0, curr_min = 0;
bool all_negative = true;
for (int num : a) {
total_sum += num;
curr_max = max(num, curr_max + num);
max_sum = max(max_sum, curr_max);
curr_min = min(num, curr_min + num);
min_sum = min(min_sum, curr_min);
if (num > 0) all_negative = false;
}
if (all_negative) return max_sum;
return max(max_sum, total_sum - min_sum);
}
};
```
## Code (Java)
```java
class Solution {
public int circularSubarraySum(int[] arr) {
int totalSum = 0, maxSum = Integer.MIN_VALUE, minSum = Integer.MAX_VALUE;
int currMax = 0, currMin = 0;
boolean allNegative = true;
for (int num : arr) {
totalSum += num;
currMax = Math.max(num, currMax + num);
maxSum = Math.max(maxSum, currMax);
currMin = Math.min(num, currMin + num);
minSum = Math.min(minSum, currMin);
if (num > 0) allNegative = false;
}
if (allNegative) return maxSum;
return Math.max(maxSum, totalSum - minSum);
}
}
```
## Code (Python)
```python
def circularSubarraySum(arr):
total_sum = 0
max_sum = float('-inf')
min_sum = float('inf')
curr_max = 0
curr_min = 0
all_negative = True
for num in arr:
total_sum += num
curr_max = max(num, curr_max + num)
max_sum = max(max_sum, curr_max)
curr_min = min(num, curr_min + num)
min_sum = min(min_sum, curr_min)
if num > 0:
all_negative = False
if all_negative:
return max_sum
return max(max_sum, total_sum - min_sum)
```
## šÆ **Contribution and Support:**
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Letās make this learning journey more collaborative!
ā If you find this helpful, please give this repository a star! ā
---
šVisitor Count
