Maximum Sum Circular Subarray

Problem

Given a circular integer array nums, return the maximum possible sum of a non-empty subarray. The array is circular: the element after nums[n-1] is nums[0]. A subarray may wrap around the end once, but no single index may be counted more than once.

Constraints

• 1 ≤ nums.length ≤ 30000
• -30000 ≤ nums[i] ≤ 30000

Approach — Dynamic Programming

This is a Dynamic Programming problem. The idea: break the problem into overlapping subproblems and build the answer up, caching results so nothing is recomputed. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) to O(n²) time.

Solution code

Python

class Solution:
    def maxSubarraySumCircular(self, nums):
        total = 0
        cur_max = best_max = nums[0]
        cur_min = best_min = nums[0]
        for i, x in enumerate(nums):
            total += x
            if i == 0:
                continue
            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)
        if best_max < 0:
            return best_max
        return max(best_max, total - best_min)

Java

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int total = 0;
        int maxSum = nums[0], curMax = 0;   // standard Kadane (best non-wrapping)
        int minSum = nums[0], curMin = 0;   // inverse Kadane (worst middle slice)
        for (int x : nums) {
            curMax = Math.max(curMax + x, x);
            maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(curMin + x, x);
            minSum = Math.min(minSum, curMin);
            total += x;
        }
        // A wrapping subarray = total minus the worst non-wrapping slice.
        // If every number is negative, total - minSum would be an empty
        // pick — fall back to the plain Kadane answer in that case.
        return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.