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

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:

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[0];
    int maxEndingHere = arr[0];

    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 maxKadane = kadane(arr, size);

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

    maxWrap = maxWrap + kadane(arr, size);

    return std::max(maxKadane, maxWrap);
}

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

    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.