Maximum Sum Circular Subarray

NeetCode: Maximum Sum Circular Subarray · LeetCode: 918. Maximum Sum Circular Subarray · Difficulty: Medium

Given a circular integer array nums (the last element is followed by the first), return the maximum sum of a non-empty subarray. A subarray may wrap around the end but may use each element at most once.

Example

Text

Input:  nums = [1, -2, 3, -2]    Output: 3
Input:  nums = [5, -3, 5]        Output: 10   (5 + 5, wrapping around)
Input:  nums = [-3, -2, -3]      Output: -2

Brute force: every start and every length

Try each start index and extend up to n elements, reading with (start + len) % n, keeping a running sum and the best sum seen. That is n starts times n lengths.

Java

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int best = Integer.MIN_VALUE;
        for (int start = 0; start < n; start++) {
            int sum = 0;
            for (int len = 0; len < n; len++) {
                sum += nums[(start + len) % n];
                best = Math.max(best, sum);
            }
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxSubarraySumCircular(new int[]{1, -2, 3, -2}));
        System.out.println(s.maxSubarraySumCircular(new int[]{5, -3, 5}));
        System.out.println(s.maxSubarraySumCircular(new int[]{-3, -2, -3}));
        System.out.println(s.maxSubarraySumCircular(new int[]{7}));
    }
}

Output

Time: O(n^2). Space: O(1).

Optimal: Kadane for the max and for the min

The best circular subarray is either an ordinary one (Kadane's algorithm) or a wrapping one. A wrapping subarray is the whole array minus a contiguous middle piece, so its sum is total - (sum of that piece); maximising it means removing the minimum-sum subarray. The answer is max(maxKadane, total - minKadane).

If every element is negative, the minimum subarray is the whole array and total - min = 0 would correspond to an empty subarray, which is not allowed. In that case maxKadane < 0 and it is the answer.

Java

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int total = 0;
        int curMax = 0, bestMax = Integer.MIN_VALUE;
        int curMin = 0, bestMin = Integer.MAX_VALUE;
        for (int x : nums) {
            total += x;
            curMax = Math.max(x, curMax + x);
            bestMax = Math.max(bestMax, curMax);
            curMin = Math.min(x, curMin + x);
            bestMin = Math.min(bestMin, curMin);
        }
        if (bestMax < 0) {
            return bestMax;
        }
        return Math.max(bestMax, total - bestMin);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxSubarraySumCircular(new int[]{1, -2, 3, -2}));
        System.out.println(s.maxSubarraySumCircular(new int[]{5, -3, 5}));
        System.out.println(s.maxSubarraySumCircular(new int[]{-3, -2, -3}));
        System.out.println(s.maxSubarraySumCircular(new int[]{7}));
    }
}

Output

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

bestMax and bestMin start at Integer.MIN_VALUE and Integer.MAX_VALUE, so every real sum replaces them on the first element. curMax + x is an int sum, so inputs with very large sums would need long.