.png)
Maximum Circular Subarray Sum
Problem Statement
You are given a circular array of integers of size n.
Find the maximum possible sum of a non-empty subarray, where the subarray may wrap around the end of the array.
In a circular array, the next element of the last index is the first index.
Example 1
Input
arr = [1, -2, 3, -2]
Output
3
Explanation
Maximum subarray is [3].
Example 2
Input
arr = [5, -3, 5]
Output
10
Explanation
Circular subarray [5, 5] gives maximum sum = 10.
Why This Problem Is Important
- Very common interview problem
- Tests understanding of Kadane’s Algorithm
- Introduces circular array optimization
- Combines max subarray and min subarray concepts
- Foundation for advanced array DP problems
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force (All Circular Subarrays) | O(n²) | O(1) |
| Approach 2 | Prefix + Wrap Handling | O(n) | O(n) |
| Approach 3 | Kadane’s Algorithm (Optimal) | O(n) | O(1) |
Approach 1: Brute Force
Idea
Check all possible subarrays considering circular wrapping and track the maximum sum.
Algorithm
- Duplicate the array (2n size)
- For each index, calculate subarray sums up to length n
- Track the maximum sum
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
Approach 1: Brute Force (All Circular Subarrays)
Idea
Check every possible circular subarray (length ≤ n) using modulo indexing and track maximum sum.
Time Complexity: O(n²)
Space Complexity: O(1)
C Implementation
#include
int max(int a, int b) {
return a > b ? a : b;
}
int circularMaxSubarraySum(int arr[], int n) {
int result = arr[0];
for(int i = 0; i < n; i++) {
int curSum = 0;
for(int j = 0; j < n; j++) {
curSum += arr[(i + j) % n];
result = max(result, curSum);
}
}
return result;
}
int main() {
int arr[] = {5, -3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int ans = circularMaxSubarraySum(arr, n);
printf("Maximum Circular Subarray Sum = %d\n", ans);
return 0;
}
Output
Maximum Circular Subarray Sum = 10
C++ Implementation
#include
using namespace std;
int circularMaxSubarraySum(int arr[], int n) {
int result = arr[0];
for(int i = 0; i < n; i++) {
int curSum = 0;
for(int j = 0; j < n; j++) {
curSum += arr[(i + j) % n];
result = max(result, curSum);
}
}
return result;
}
int main() {
int arr[] = {5, -3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int ans = circularMaxSubarraySum(arr, n);
cout << "Maximum Circular Subarray Sum = " << ans << endl;
return 0;
}
Output
Maximum Circular Subarray Sum = 10
Java Implementation
public class CircularSubarrayBrute {
public static int circularMaxSubarraySum(int[] arr) {
int n = arr.length;
int result = arr[0];
for(int i = 0; i < n; i++) {
int curSum = 0;
for(int j = 0; j < n; j++) {
curSum += arr[(i + j) % n];
result = Math.max(result, curSum);
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {5, -3, 5};
int ans = circularMaxSubarraySum(arr);
System.out.println("Maximum Circular Subarray Sum = " + ans);
}
}
Output
Maximum Circular Subarray Sum = 10
Python Implementation
def circular_max_subarray_sum(arr):
n = len(arr)
result = arr[0]
for i in range(n):
cur_sum = 0
for j in range(n):
cur_sum += arr[(i + j) % n]
result = max(result, cur_sum)
return result
arr = [5, -3, 5]
ans = circular_max_subarray_sum(arr)
print("Maximum Circular Subarray Sum =", ans)
Output
Maximum Circular Subarray Sum = 10
JavaScript Implementation
function circularMaxSubarraySum(arr) {
let n = arr.length;
let result = arr[0];
for (let i = 0; i < n; i++) {
let curSum = 0;
for (let j = 0; j < n; j++) {
curSum += arr[(i + j) % n];
result = Math.max(result, curSum);
}
}
return result;
}
let arr = [5, -3, 5];
let ans = circularMaxSubarraySum(arr);
console.log("Maximum Circular Subarray Sum =", ans);
Output
Maximum Circular Subarray Sum = 10
Approach 2: Prefix Sum + Circular Handling
Idea
Use prefix sums to calculate wrap-around subarrays efficiently.
Algorithm
- Create prefix sum array of duplicated array
- Compute maximum subarray sum with length ≤ n
- Track the maximum
Time & Space Complexity
- Time: O(n)
- Space: O(n)
C Implementation
#include
#include
int max(int a, int b) {
return a > b ? a : b;
}
int circularMaxSubarraySum(int arr[], int n) {
int prefix[2*n + 1];
prefix[0] = 0;
// Build prefix sum for duplicated array
for(int i = 0; i < 2*n; i++) {
prefix[i+1] = prefix[i] + arr[i % n];
}
int result = INT_MIN;
// Calculate all circular subarrays of length <= n
for(int i = 0; i < n; i++) {
for(int j = i+1; j <= i+n; j++) {
int sum = prefix[j] - prefix[i];
result = max(result, sum);
}
}
return result;
}
int main() {
int arr[] = {5, -3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int ans = circularMaxSubarraySum(arr, n);
printf("Maximum Circular Subarray Sum = %d\n", ans);
return 0;
}
Output
Maximum Circular Subarray Sum = 10
C++ Implementation
#include
#include
#include
using namespace std;
int circularMaxSubarraySum(vector& arr) {
int n = arr.size();
vector prefix(2*n + 1, 0);
// Build prefix sum of duplicated array
for(int i = 0; i < 2*n; i++) {
prefix[i+1] = prefix[i] + arr[i % n];
}
int result = INT_MIN;
// Evaluate all circular subarrays
for(int i = 0; i < n; i++) {
for(int j = i+1; j <= i+n; j++) {
int sum = prefix[j] - prefix[i];
result = max(result, sum);
}
}
return result;
}
int main() {
vector arr = {5, -3, 5};
int ans = circularMaxSubarraySum(arr);
cout << "Maximum Circular Subarray Sum = " << ans << endl;
return 0;
}
Output
Maximum Circular Subarray Sum = 10
Java Implementation
public class CircularSubarrayPrefix {
public static int circularMaxSubarraySum(int[] arr) {
int n = arr.length;
int[] prefix = new int[2*n + 1];
// Build prefix sum of duplicated array
for(int i = 0; i < 2*n; i++) {
prefix[i+1] = prefix[i] + arr[i % n];
}
int result = Integer.MIN_VALUE;
// Evaluate circular subarrays
for(int i = 0; i < n; i++) {
for(int j = i+1; j <= i+n; j++) {
int sum = prefix[j] - prefix[i];
result = Math.max(result, sum);
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {5, -3, 5};
int ans = circularMaxSubarraySum(arr);
System.out.println("Maximum Circular Subarray Sum = " + ans);
}
}
Output
Maximum Circular Subarray Sum = 10
Python Implementation
def circular_max_subarray_sum(arr):
n = len(arr)
prefix = [0] * (2*n + 1)
# Build prefix sum of duplicated array
for i in range(2*n):
prefix[i+1] = prefix[i] + arr[i % n]
result = float('-inf')
# Evaluate circular subarrays
for i in range(n):
for j in range(i+1, i+n+1):
sum_val = prefix[j] - prefix[i]
result = max(result, sum_val)
return result
arr = [5, -3, 5]
ans = circular_max_subarray_sum(arr)
print("Maximum Circular Subarray Sum =", ans)
Output
Maximum Circular Subarray Sum = 10
JavaScript Implementation
function circularMaxSubarraySum(arr) {
let n = arr.length;
let prefix = new Array(2*n + 1).fill(0);
// Build prefix sum of duplicated array
for (let i = 0; i < 2*n; i++) {
prefix[i+1] = prefix[i] + arr[i % n];
}
let result = -Infinity;
// Evaluate circular subarrays
for (let i = 0; i < n; i++) {
for (let j = i+1; j <= i+n; j++) {
let sum = prefix[j] - prefix[i];
result = Math.max(result, sum);
}
}
return result;
}
let arr = [5, -3, 5];
let ans = circularMaxSubarraySum(arr);
console.log("Maximum Circular Subarray Sum =", ans);
Output
Maximum Circular Subarray Sum = 10
Approach 3: Kadane’s Algorithm (Optimal)
Key Insight
Maximum Circular Subarray Sum is either:
- Normal maximum subarray sum (Kadane’s)
- Total sum – minimum subarray sum
Final Answer:
max(maxSubarraySum, totalSum - minSubarraySum)
Edge Case:
If all elements are negative, return maxSubarraySum.
Algorithm
- Use Kadane’s Algorithm to find:
- maxSubarraySum
- minSubarraySum
- Compute totalSum of the array
- If maxSubarraySum < 0, return it
- Else return max(maxSubarraySum, totalSum - minSubarraySum)
Time & Space Complexity
- Time: O(n)
- Space: O(1)
Approach 3: Kadane’s Algorithm
Key Insight
Maximum Circular Subarray Sum is:
max( normal_kadane , totalSum - min_kadane )
If all elements are negative → return normal_kadane.
Time Complexity: O(n)
Space Complexity: O(1)
C Implementation
#include
int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }
int circularMaxSubarraySum(int arr[], int n) {
int totalSum = 0;
int maxSum = arr[0], curMax = 0;
int minSum = arr[0], curMin = 0;
for(int i = 0; i < n; i++) {
curMax = max(arr[i], curMax + arr[i]);
maxSum = max(maxSum, curMax);
curMin = min(arr[i], curMin + arr[i]);
minSum = min(minSum, curMin);
totalSum += arr[i];
}
if(maxSum < 0)
return maxSum;
return max(maxSum, totalSum - minSum);
}
int main() {
int arr[] = {5, -3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int ans = circularMaxSubarraySum(arr, n);
printf("Maximum Circular Subarray Sum = %d\n", ans);
return 0;
}
Output
Maximum Circular Subarray Sum = 10
C++ Implementation
#include
using namespace std;
int circularMaxSubarraySum(int arr[], int n) {
int totalSum = 0;
int maxSum = arr[0], curMax = 0;
int minSum = arr[0], curMin = 0;
for(int i = 0; i < n; i++) {
curMax = max(arr[i], curMax + arr[i]);
maxSum = max(maxSum, curMax);
curMin = min(arr[i], curMin + arr[i]);
minSum = min(minSum, curMin);
totalSum += arr[i];
}
if(maxSum < 0)
return maxSum;
return max(maxSum, totalSum - minSum);
}
int main() {
int arr[] = {5, -3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int ans = circularMaxSubarraySum(arr, n);
cout << "Maximum Circular Subarray Sum = " << ans << endl;
return 0;
}Output
Maximum Circular Subarray Sum = 10 Java Implementation
public class MaximumCircularSubarraySum {
public static int circularMaxSubarraySum(int[] arr) {
int totalSum = 0;
int maxSum = arr[0], curMax = 0;
int minSum = arr[0], curMin = 0;
for(int num : arr) {
curMax = Math.max(num, curMax + num);
maxSum = Math.max(maxSum, curMax);
curMin = Math.min(num, curMin + num);
minSum = Math.min(minSum, curMin);
totalSum += num;
}
if(maxSum < 0)
return maxSum;
return Math.max(maxSum, totalSum - minSum);
}
public static void main(String[] args) {
int[] arr = {5, -3, 5};
int ans = circularMaxSubarraySum(arr);
System.out.println("Maximum Circular Subarray Sum = " + ans);
}
}
Output
Maximum Circular Subarray Sum = 10 Python Implementation
def circular_max_subarray_sum(arr):
total_sum = 0
max_sum = arr[0]
min_sum = arr[0]
cur_max = 0
cur_min = 0
for num in arr:
cur_max = max(num, cur_max + num)
max_sum = max(max_sum, cur_max)
cur_min = min(num, cur_min + num)
min_sum = min(min_sum, cur_min)
total_sum += num
if max_sum < 0:
return max_sum
return max(max_sum, total_sum - min_sum)
arr = [5, -3, 5]
ans = circular_max_subarray_sum(arr)
print("Maximum Circular Subarray Sum =", ans)
Output
Maximum Circular Subarray Sum = 10 JavaScript Implementation
function circularMaxSubarraySum(arr) {
let totalSum = 0;
let maxSum = arr[0], curMax = 0;
let minSum = arr[0], curMin = 0;
for (let num of arr) {
curMax = Math.max(num, curMax + num);
maxSum = Math.max(maxSum, curMax);
curMin = Math.min(num, curMin + num);
minSum = Math.min(minSum, curMin);
totalSum += num;
}
if (maxSum < 0)
return maxSum;
return Math.max(maxSum, totalSum - minSum);
}
let arr = [5, -3, 5];
let ans = circularMaxSubarraySum(arr);
console.log("Maximum Circular Subarray Sum =", ans);
Output
Maximum Circular Subarray Sum = 10
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
