Max sum in Circular Subarray [Max - Min Subarray]

918.Maximum Sum Circular Subarray

Array

Dynamic Programming

Kadane's Algorithm

Problem Statement:

Given a circular integer array nums, return the maximum possible sum of a non-empty subarray of nums. A circular array means the end of the array connects to the beginning of the array.

Example:

Input:

nums = [1,-2,3,-2]

→

Output:

3

Subarray [3] has maximum sum 3.
Note: In circular case [4,-1,2,1] would form by connecting end to beginning.

Key Insights:

1. Maximum sum can be either:
   • Regular subarray (use Kadane's Algorithm)
   • Circular subarray (totalSum - minimum subarray sum)
2. Special case: If all numbers are negative, return maximum element
3. Use Kadane's Algorithm twice: once for max sum, once for min sum

Algorithm:

1. Track four values:
   • maxSum: largest regular subarray sum
   • minSum: smallest regular subarray sum
   • totalSum: sum of all elements
   • curMax/curMin: current running sums
2. For all negative arrays, return maxSum
3. Otherwise, return max(maxSum, totalSum - minSum)

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public int maxSubarraySumCircular(int[] A) {
    // Variables to track various sums
    int totalSum = 0; 
    int maxSum = Integer.MIN_VALUE, curMax = 0;
    int minSum = Integer.MAX_VALUE, curMin = 0;
    
    for (int num : A) {
        // Kadane's algorithm for maximum subarray
        curMax = Math.max(curMax + num, num);
        maxSum = Math.max(maxSum, curMax);
        
        // Kadane's algorithm for minimum subarray
        curMin = Math.min(curMin + num, num);
        minSum = Math.min(minSum, curMin);
        
        totalSum += num;
    }
    
    // If all numbers negative, return the largest one
    if (maxSum < 0) return maxSum;
    
    // Return max of regular and circular case
    return Math.max(maxSum, totalSum - minSum);
}

Python Solution:

def maxSubarraySumCircular(self, nums: List[int]) -> int:
    total_sum = 0
    cur_max = max_sum = float('-inf')
    cur_min = min_sum = float('inf')
    
    for num in nums:
        # Maximum subarray sum
        cur_max = max(num, cur_max + num)
        max_sum = max(max_sum, cur_max)
        
        # Minimum subarray sum
        cur_min = min(num, cur_min + num)
        min_sum = min(min_sum, cur_min)
        
        total_sum += num
    
    return max_sum if max_sum < 0 else max(max_sum, total_sum - min_sum)

C++ Solution:

int maxSubarraySumCircular(vector<int>& A) {
    int total_sum = 0;
    int max_sum = INT_MIN, cur_max = 0;
    int min_sum = INT_MAX, cur_min = 0;
    
    for (int num : A) {
        // Track maximum subarray
        cur_max = max(num, cur_max + num);
        max_sum = max(max_sum, cur_max);
        
        // Track minimum subarray
        cur_min = min(num, cur_min + num);
        min_sum = min(min_sum, cur_min);
        
        total_sum += num;
    }
    
    return max_sum < 0 ? max_sum : 
           max(max_sum, total_sum - min_sum);
}