Sponsored
Sponsored
The main idea is to use Kadane's Algorithm to find the maximum subarray sum for two scenarios: one, where the subarray wraps around the end and beginning of the array, and two, where it does not.
Calculate the maximum subarray sum using Kadane's algorithm in the normal way. Then calculate the minimum subarray sum using a similar technique but by negating the result. The maximum possible circular subarray sum will be the maximum value between the normal subarray sum and the total array sum minus the minimum subarray sum.
Time Complexity: O(n) — as both the applications of Kadane's algorithm are linear.
Space Complexity: O(1) — no additional space is used except for a few variables.
1public class Solution {
2 public int MaxSubarraySumCircular(int[] A) {
3 int sumAll = 0;
4
5 foreach (int a in A) sumAll += a; // Total sum of array
6
7 int maxCurrent = A[0], maxGlobal = A[0];
8 for (int i = 1; i < A.Length; i++) {
9 maxCurrent = Math.Max(A[i], maxCurrent + A[i]);
10 maxGlobal = Math.Max(maxGlobal, maxCurrent);
11 }
12
13 int minCurrent = A[0], minGlobal = A[0];
for (int i = 1; i < A.Length; i++) {
minCurrent = Math.Min(A[i], minCurrent + A[i]);
minGlobal = Math.Min(minGlobal, minCurrent);
}
int maxCircular = sumAll - minGlobal;
return maxCircular == 0 ? maxGlobal : Math.Max(maxGlobal, maxCircular);
}
}The C# solution follows a similar logic to its Java counterpart. By calculating the overall maximum subarray with Kadane's and the minimum (derived via negation), it offers both paths for a non-circular or circular subarray sum, ultimately comparing and returning the best choice.
Instead of using basic Kadane's approach, we can consider computing the maximum subarray sum with additional memory for storing maximum and minimum values up to each index. This allows precise tracing of subarrays—as contiguous and potential wrap-around cases.
Time Complexity: O(n)
Space Complexity: O(1)
1#include <vector>
#include <algorithm>
int maxSubarraySumCircular(std::vector<int>& nums) {
int total = 0, max_sum = nums[0], min_sum = nums[0];
int cur_max = 0, cur_min = 0;
for (int num : nums) {
cur_max = std::max(cur_max + num, num);
max_sum = std::max(max_sum, cur_max);
cur_min = std::min(cur_min + num, num);
min_sum = std::min(min_sum, cur_min);
total += num;
}
return (max_sum < 0) ? max_sum : std::max(max_sum, total - min_sum);
}Through utilizing the flexibility of C++ built-in methods, we solve the problem by maintaining totals and conditionally updating minimum and maximum traversal outcomes. This efficiently constructs results to verify and return at the term end.