Solution For Maximum Sum Circular Subarray
The Maximum Sum Circular Subarray problem on LeetCode can be solved using the Kadane’s algorithm and a little bit of modification to handle the circular subarray case. The problem statement is as follows:
Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.
Example:
Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3
Algorithm:
Find the maximum subarray sum using Kadane’s algorithm. This will give the maximum sum when there are no circular shifts.
Find the minimum subarray sum using the same algorithm but by negating the array elements. This will give us the minimum sum when there are no circular shifts.
Compute the total sum of the array.
Compute the circular sum by subtracting the minimum sum from the total sum. This will give us the maximum sum when there is one circular shift.
Return the maximum of step 1 and step 4.
Pseudo code:
def maxSubarraySumCircular(nums):
max_sum = nums[0]
min_sum = nums[0]
curr_max = nums[0]
curr_min = nums[0]
total_sum = nums[0]
n = len(nums)
# Compute the maximum and minimum subarray sums
for i in range(1, n):
curr_max = max(curr_max + nums[i], nums[i])
max_sum = max(max_sum, curr_max)
curr_min = min(curr_min + nums[i], nums[i])
min_sum = min(min_sum, curr_min)
total_sum += nums[i]
# Compute the circular sum
circular_sum = total_sum - (-min_sum) # Negate min_sum to convert it to max_sum
# Return the maximum of normal and circular subarray sums
return max(max_sum, circular_sum)
Time complexity: O(n)
Space complexity: O(1)
Step by Step Implementation For Maximum Sum Circular Subarray
class Solution { public int maxSubarraySumCircular(int[] A) { int total = 0; int maxSum = Integer.MIN_VALUE; int currMax = 0; int minSum = Integer.MAX_VALUE; int currMin = 0; for (int a : A) { currMax = Math.max(currMax + a, a); maxSum = Math.max(maxSum, currMax); currMin = Math.min(currMin + a, a); minSum = Math.min(minSum, currMin); total += a; } return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum; } }
class Solution: def maxSubarraySumCircular(self, A: List[int]) -> int: # kadane's algorithm to find maximum subarray sum # for a given array max_sum = A[0] curr_max = A[0] for i in range(1, len(A)): curr_max = max(A[i], curr_max + A[i]) max_sum = max(max_sum, curr_max) # for minimum subarray sum min_sum = A[0] curr_min = A[0] for i in range(1, len(A)): curr_min = min(A[i], curr_min + A[i]) min_sum = min(min_sum, curr_min) # in case all values in the array are negative if max_sum == min_sum: return max_sum # otherwise return maximum of maximum subarray sum # found by kadane's algorithm and total sum - minimum # subarray sum return max(max_sum, sum(A) - min_sum)
var maxSubarraySumCircular = function(A) { let N = A.length let ans = A[0], cur = A[0] for (let i = 1; i < N; ++i) { cur = A[i] + Math.max(cur, 0) ans = Math.max(ans, cur) } // ans is the answer for 1-interval subarrays. // Now, let's consider all 2-interval subarrays. // For each i, we want to know // the maximum of sum(A[j:]) with j >= i+2 // rightsums[i] = A[i] + A[i+1] + ... + A[N-1] let rightsums = new Array(N).fill(0) rightsums[N-1] = A[N-1] for (let i = N-2; i >= 0; --i) rightsums[i] = rightsums[i+1] + A[i] // maxright[i] = max_{j >= i} rightsums[j] let maxright = new Array(N).fill(0) maxright[N-1] = A[N-1] for (let i = N-2; i >= 0; --i) maxright[i] = Math.max(maxright[i+1], rightsums[i]) let leftsum = 0 for (let i = 1; i < N-1; ++i) { leftsum += A[i-1] ans = Math.max(ans, leftsum + maxright[i+1]) } return ans };
class Solution { public: int maxSubarraySumCircular(vector& A) { int total = 0, maxSum = -30000, curMax = 0, minSum = 30000, curMin = 0; for (int a : A) { curMax = max(curMax + a, a); maxSum = max(maxSum, curMax); curMin = min(curMin + a, a); minSum = min(minSum, curMin); total += a; } return maxSum > 0 ? max(maxSum, total - minSum) : maxSum; } };
public int MaxSubarraySumCircular(int[] A) { //Kadane's algorithm to find maximum sum subarray int max_so_far = A[0], max_ending_here = A[0]; for (int i = 1; i < A.Length; i++) { /* Find maximum sum subarray having start and end indices as i and j */ max_ending_here = Math.Max(max_ending_here + A[i], A[i]); /* Update result if this sum is found to be maximum so far */ if (max_so_far < max_ending_here) max_so_far = max_ending_here; } //In case all numbers are negative, return maximum of the array if (max_so_far < 0) return max_so_far; //Otherwise, return maximum sum of a non-empty subarray int max_wrap = 0, min_wrap = 0; for (int i = 0; i < A.Length; i++) { max_wrap += A[i]; min_wrap += A[i]; A[i] = -A[i]; } //max sum with corner elements will be: //array-sum - (-max subarray sum of A) max_wrap = max_wrap + MaxSubarraySumCircular(A); //Similarly, calculate minimum sum subarray (Needs //to be done as second step as we have modified original //array) MinSubArraySum(A); min_wrap = min_wrap + min_wrap_sum; //The maximum circular sum will be maximum of two sums return (max_wrap > min_wrap)? max_wrap: min_wrap; } static int min_wrap_sum = int.MaxValue; //utility function to find minimum sum subarray static void MinSubArraySum(int []arr) { //Kadane's algorithm to find minimum sum subarray int min_so_far = arr[0], min_ending_here = arr[0]; for (int i = 1; i < arr.Length; i++) { /* Find minimum sum subarray having start and end indices as i and j */ min_ending_here = Math.Min(min_ending_here + arr[i], arr[i]); /* Update result if this sum is found to be minimum so far */ if (min_so_far > min_ending_here) min_so_far = min_ending_here; } min_wrap_sum = min_so_far; }