# Maximum Circular Subarray Sum (with code)

In this article, we will delve into the intricacies of the maximum circular subarray sum problem, explore different algorithms to solve it efficiently and discuss its practical applications.

## Maximum Circular Subarray Sum

The maximum circular subarray sum problem is a common challenge in computer science and algorithms. It involves finding the maximum sum of a subarray in a circular manner, where the subarray can wrap around from the end of the array to the beginning. This problem has various applications, including data analysis, financial modeling, and optimization algorithms.

Here is the Problem: Given an array of integers, the maximum circular subarray sum problem requires finding a contiguous subarray with the largest possible sum, allowing the subarray to wrap around the array's boundary. The circular aspect means that the subarray can start from the end of the array and continue at the beginning, forming a circular loop.

The maximum circular subarray sum problem has applications in data analysis, resource allocation, and image processing. By identifying the circular subarray with the maximum sum, algorithms can detect circular objects, such as coins in a coin counting application.

Kadane's algorithm is a popular and efficient algorithm for finding the maximum subarray sum within an array. It solves the problem in a single pass through the array, making it a linear-time solution. Kadane's algorithm can be extended to find the maximum circular subarray sum. Here's how you can modify Kadane's algorithm to solve this problem:

1. Find the maximum subarray sum using Kadane's algorithm:

• Start by initializing two variables, `maxSoFar` and `maxEndingHere`, to the value of the first element in the array.
• Iterate through the array, starting from the second element.
• For each element `num` in the array:
• Update `maxEndingHere` by taking the maximum value between `num` and the sum of `num` and `maxEndingHere`.
• Update `maxSoFar` by taking the maximum value between `maxSoFar` and `maxEndingHere`.
• This step finds the maximum subarray sum within the original array.
2. Find the maximum circular subarray sum:

• Calculate the total sum of all elements in the array and store it in a variable called `totalSum`.
• Invert the signs of all elements in the array. This can be done by multiplying each element by -1.
• Apply Kadane's algorithm to find the minimum subarray sum within the inverted array. Let's call this value `minSubarraySum`.
• Calculate the maximum circular subarray sum by subtracting `minSubarraySum` from `totalSum`. Let's call this value `maxCircularSum`.
• The maximum circular subarray sum is the maximum between `maxCircularSum` and the maximum subarray sum obtained in step 1 (`maxSoFar`).
3. Return the maximum circular subarray sum as the result.

The modified Kadane's algorithm for maximum circular subarray sum takes into account the possibility of the subarray wrapping around from the end to the beginning of the array. By inverting the signs of the elements and applying Kadane's algorithm, we can find the minimum subarray sum within the inverted array, which corresponds to the maximum circular subarray sum in the original array.

Note that if the array contains all negative elements, the maximum circular subarray sum would be the same as the maximum subarray sum within the array.

### Max Sum Circular Subarray Example

Let's consider the following example to demonstrate the maximum circular subarray problem:

Input: [8, -4, 3, -5, 4]

To find the maximum circular subarray sum, we can apply Kadane's algorithm with a slight modification.

Step 1: Finding the maximum subarray sum using Kadane's algorithm:

• `maxSoFar` = 8, `maxEndingHere` = 8
• Move to the next element, -4:
• Update `maxEndingHere` to the maximum between -4 and -4 + 8, which is 4.
• Update `maxSoFar` to 8 (no change).
• Move to the next element, 3:
• Update `maxEndingHere` to the maximum between 3 and 3 + 4, which is 7.
• Update `maxSoFar` to 8 (no change).
• Move to the next element, -5:
• Update `maxEndingHere` to the maximum between -5 and -5 + 7, which is 2.
• Update `maxSoFar` to 8 (no change).
• Move to the last element, 4:
• Update `maxEndingHere` to the maximum between 4 and 4 + 2, which is 6.
• Update `maxSoFar` to 8 (no change).

The maximum subarray sum within the original array is 8.

Step 2: Finding the maximum circular subarray sum:

• Calculate the total sum of all elements: 8 - 4 + 3 - 5 + 4 = 6.
• Invert the signs of the elements: -8, 4, -3, 5, -4.
• Apply Kadane's algorithm to find the minimum subarray sum within the inverted array:
• `maxSoFar` = -8, `maxEndingHere` = -8.
• Move to the next element, 4:
• Update `maxEndingHere` to the maximum between 4 and 4 - 8, which is 4.
• Update `maxSoFar` to 4 (no change).
• Move to the next element, -3:
• Update `maxEndingHere` to the maximum between -3 and -3 + 4, which is 1.
• Update `maxSoFar` to 4 (no change).
• Move to the next element, 5:
• Update `maxEndingHere` to the maximum between 5 and 5 + 1, which is 6.
• Update `maxSoFar` to 6 (no change).
• Move to the last element, -4:
• Update `maxEndingHere` to the maximum between -4 and -4 + 6, which is 2.
• Update `maxSoFar` to 6 (no change).

The minimum subarray sum within the inverted array is 6.

Calculate the maximum circular subarray sum by subtracting the minimum subarray sum from the total sum: 6 - 6 = 0.

The maximum circular subarray sum is 8, which is the same as the maximum subarray sum within the original array.

In conclusion, for the given example, the maximum circular subarray sum is 8.

### Max Sum Circular Subarray Implementation

Here's the code in C++ to find the maximum circular subarray sum using Kadane's algorithm:

```#include
#include

int kadane(int arr[], int size) {
int maxSoFar = arr;
int maxEndingHere = arr;

for (int i = 1; i < size; i++) {
maxEndingHere = std::max(arr[i], maxEndingHere + arr[i]);
maxSoFar = std::max(maxSoFar, maxEndingHere);
}

return maxSoFar;
}

int maxCircularSubarraySum(int arr[], int size) {

int maxWrap = 0;
for (int i = 0; i < size; i++) {
maxWrap += arr[i];
arr[i] = -arr[i];
}

maxWrap = maxWrap + kadane(arr, size);

}

int main() {
int arr[] = { 8, -4, 3, -5, 4 };
int size = sizeof(arr) / sizeof(arr);

int maxSum = maxCircularSubarraySum(arr, size);

std::cout << "Maximum circular subarray sum: " << maxSum << std::endl;

return 0;
}
```

#### Output:

`Maximum circular subarray sum: 12`

In this code, we first define a helper function `kadane` that implements Kadane's algorithm to find the maximum subarray sum within a regular array.

The `maxCircularSubarraySum` function takes an array `arr` and its size as input and returns the maximum circular subarray sum. It uses the `kadane` function to find the maximum subarray sum within the original array.

To find the maximum circular subarray sum, we need to consider two cases:

1. The maximum subarray sum lies entirely within the array (same as finding the maximum subarray sum using Kadane's algorithm).
2. The maximum subarray sum wraps around from the end to the beginning of the array.

We calculate the maximum subarray sum in the second case by changing the sign of each element in the array and applying Kadane's algorithm again. We add this value to the sum of all elements in the array (`maxWrap`).

Finally, we return the maximum value between the two cases: `maxKadane` (maximum subarray sum within the array) and `maxWrap` (maximum subarray sum wrapping around the array).

### Space & Time Complexity

Finding the maximum subarray sum using Kadane's algorithm requires a single pass through the array, resulting in a time complexity of O(n), where n is the size of the input array. Inverting the signs of the array elements and applying Kadane's algorithm again also requires a single pass through the array, resulting in an additional time complexity of O(n).

Therefore, the overall time complexity of the code is O(n), where n is the size of the input array.

The code has a space complexity of O(1) because it only uses a constant amount of additional space to store variables such as `maxSoFar`, `maxEndingHere`, `totalSum`, and `minSubarraySum`. Regardless of the size of the input array, the space used remains the same, resulting in constant space complexity.

## Takeaways

The maximum circular subarray sum problem presents an intriguing challenge in the coding world, and Kadane's algorithm to solve it. It can be used in Finance Modeling to analyze investment returns as well.

### FavTutor - 24x7 Live Coding Help from Expert Tutors! 