Maximum Sum Circular Subarray

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

Input: nums = [1,-2,3,-2]
Output:3
Explanation: Subarray [3] has maximum sum 3.

Maximum Sum Circular Subarray Using Kadan's Algorithm

    
        class Solution {
            public int maxSubarraySumCircular(int[] nums) {
                if (nums.length == 1)
                  return nums[0];
                
                int sum = 0;
                for (int i = 0; i < nums.length; i++) {
                  sum += nums[i];
                }
        
                int currrent_max = nums[0], current_min = nums[0];
                int maxSum =nums[0], minSum = nums[0];
        
                //Kadanes Algorithm
                for (int i = 1; i < nums.length; i++){
                  currrent_max = Math.max(currrent_max + nums[i], nums[i]);
                  maxSum = Math.max(maxSum, currrent_max); //find Maximum subarray sum
        
                  current_min = Math.min(current_min + nums[i], nums[i]);
                  minSum = Math.min(minSum, current_min); //find Minimum subarray sum
                }
                
                if (minSum == sum) {
                  return maxSum;
                }
                return Math.max(maxSum, sum - minSum);
            }
        }        
    

Explanation

This code finds the maximum sum of a subarray in a circular array. A circular array allows the array to "wrap around," meaning the end of the array is connected to its beginning.

Key Variables

• sum: The total sum of the array.
• currrent_max: Tracks the maximum sum of the subarray ending at the current index.
• maxSum: The overall maximum subarray sum using Kadane's algorithm.
• current_min: Tracks the minimum sum of the subarray ending at the current index.
• minSum: The overall minimum subarray sum using Kadane's algorithm.

Algorithm

1. Edge Case: If the array has only one element, return that element.

2. Calculate the total sum of the array and initialize variables for tracking maximum and minimum subarray sums.

3. Use Kadane's algorithm:

   • For maximum subarray sum:

     • At each index, calculate the maximum of extending the current subarray or starting a new one.

     • Update the overall maxSum.

   • For minimum subarray sum:

     • At each index, calculate the minimum of extending the current subarray or starting a new one.

     • Update the overall minSum.

4. If the minimum subarray sum equals the total sum, it means all numbers are negative. Return maxSum.

5. Otherwise, return the maximum of maxSum and sum - minSum (to handle circular cases).

Complexity Analysis

• Time Complexity: O(n)

  • The algorithm iterates through the array once to compute the total sum, maximum, and minimum subarray sums.

• Space Complexity: O(1)

  • The algorithm uses a constant amount of additional space.