Practice › Arrays
Maximum Circular Subarray Sum
Medium · Arrays · Asked at Amazon, Microsoft, Adobe, Goldman Sachs
The array is circular (the last element is followed by the first). Print the maximum sum of a non-empty subarray, where a subarray may wrap around the end but may use each element at most once.
Input
First line: n. Second line: n space-separated integers.
Output
The maximum circular subarray sum.
Constraints
- 1 ≤ n ≤ 10^5
- -10^4 ≤ a[i] ≤ 10^4
Answer = max(normal Kadane, total − minimum subarray). If every number is negative, the second option is empty — use Kadane's result.
Example 1
Input
3 5 -3 5
Output
10
Example 2
Input
3 -3 -2 -3
Output
-2
Hints
- A non-wrapping answer is ordinary Kadane's.
- A wrapping subarray leaves out a contiguous middle part — so its sum is total − (minimum subarray sum).
Approach
Run Kadane twice in one pass: maxSub (best normal subarray) and minSub (smallest subarray). The best wrapping subarray is total − minSub. Answer = max(maxSub, total − minSub) — except when all numbers are negative: then minSub = total, the "wrapping" option would be the empty subarray, so answer maxSub.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
long long total = 0, curMax = 0, curMin = 0, maxSub = LLONG_MIN, minSub = LLONG_MAX, x;
for (int i = 0; i < n; i++) {
cin >> x;
total += x;
curMax = max(x, curMax + x);
maxSub = max(maxSub, curMax);
curMin = min(x, curMin + x);
minSub = min(minSub, curMin);
}
cout << (maxSub < 0 ? maxSub : max(maxSub, total - minSub)) << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
a = data[1:]
total = cur_max = cur_min = 0
max_sub, min_sub = float("-inf"), float("inf")
for x in a:
total += x
cur_max = max(x, cur_max + x)
max_sub = max(max_sub, cur_max)
cur_min = min(x, cur_min + x)
min_sub = min(min_sub, cur_min)
print(max_sub if max_sub < 0 else max(max_sub, total - min_sub))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long total = 0, curMax = 0, curMin = 0, maxSub = Long.MIN_VALUE, minSub = Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
long x = sc.nextLong();
total += x;
curMax = Math.max(x, curMax + x);
maxSub = Math.max(maxSub, curMax);
curMin = Math.min(x, curMin + x);
minSub = Math.min(minSub, curMin);
}
System.out.println(maxSub < 0 ? maxSub : Math.max(maxSub, total - minSub));
}
}Solve Maximum Circular Subarray Sum online · All practice problems