Largest Sum in a Circular Array

medium array dp kadane

Problem

Given a circular integer array, return the maximum non-empty subarray sum. A subarray may wrap around the end into the beginning, but each index is used at most once.

Either the best subarray is contiguous (standard Kadane gives maxSum) or it wraps. The wrapping case is the complement of the smallest contiguous subarray, so its sum is total − minSum. Return max(maxSum, total − minSum). Edge case: if every element is negative, total − minSum is 0 (empty complement) — fall back to maxSum.

Inputnums = [5, -3, 5]

Output10

Total 7, minSum -3 → wrap = 7 − (−3) = 10. maxSum (no wrap) = 7. Answer: 10.

nums (comma-separated)

def max_circular(nums):
    total = 0
    cur_max = best_max = nums[0]
    cur_min = best_min = nums[0]
    total += nums[0]
    for x in nums[1:]:
        cur_max = max(x, cur_max + x); best_max = max(best_max, cur_max)
        cur_min = min(x, cur_min + x); best_min = min(best_min, cur_min)
        total += x
    if best_max < 0: return best_max
    return max(best_max, total - best_min)

function maxCircular(nums) {
  let total = nums[0];
  let curMax = nums[0], bestMax = nums[0];
  let curMin = nums[0], bestMin = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const x = nums[i];
    curMax = Math.max(x, curMax + x); bestMax = Math.max(bestMax, curMax);
    curMin = Math.min(x, curMin + x); bestMin = Math.min(bestMin, curMin);
    total += x;
  }
  if (bestMax < 0) return bestMax;
  return Math.max(bestMax, total - bestMin);
}

public int maxCircular(int[] nums) {
    int total = nums[0];
    int curMax = nums[0], bestMax = nums[0];
    int curMin = nums[0], bestMin = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int x = nums[i];
        curMax = Math.max(x, curMax + x); bestMax = Math.max(bestMax, curMax);
        curMin = Math.min(x, curMin + x); bestMin = Math.min(bestMin, curMin);
        total += x;
    }
    if (bestMax < 0) return bestMax;
    return Math.max(bestMax, total - bestMin);
}

int maxCircular(vector<int>& nums) {
    int total = nums[0];
    int curMax = nums[0], bestMax = nums[0];
    int curMin = nums[0], bestMin = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        int x = nums[i];
        curMax = max(x, curMax + x); bestMax = max(bestMax, curMax);
        curMin = min(x, curMin + x); bestMin = min(bestMin, curMin);
        total += x;
    }
    if (bestMax < 0) return bestMax;
    return max(bestMax, total - bestMin);
}

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