[LeetCode] Maximum Sum Circular Subarray

Problem: Given a circular integer array nums of length n, 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. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.

Example:

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

Input: nums = [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.

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

Approach: This problem is an extension of Kadanes max sum problem. If you see if the max sum exist in the middle than Kadanes approach is sufficient but if the max sum exist in circular subarray then we need to come up with a different approach.

Let's say the other special sum in case of circular array is called circular sum. How does it look like:

So if you see above array, you will understand

circular sum = sum of prefix of array + sum of suffix of array.

Now we just need to get max of all such calculated circular sums. To do it efficiently, we can prepopulate a rightmax array where rightmax[i] is the max sum of subarray nums[i...n-1]. With this we can easily calculate the max sum which is:

max_sum = MAX(kadanes_max_sum, max_circular_sum)

This is time efficient but if you see the above approach is iterating the input array twice and is using extra space in the form of rightmax array. Let's try to do better.

If you see max_circular_sum is equal to total sum of array - kadanes_min_sum. Right! We can calculate it using kadanes min sum with same approach by which we get kadanes max sum. It's just that we need to use Min instead of Max in the algo.

The only exception will be when all the numbers are negative which is easy to handle as in that case we just need to return kadanes_max_sum.

That's all!

Implementation in C#:

Approach 1: Using extra space:

    public int MaxSubarraySumCircular(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        if (length == 1)

        {

            return nums[0];

        }

        int[] rightMax = new int[length];

        rightMax[length - 1] = nums[length - 1];

        int suffixSum = nums[length - 1];

        for (int i = length - 2; i >= 0; --i)

        {

            suffixSum += nums[i];

            rightMax[i] = Math.Max(suffixSum, rightMax[i + 1]);

        }

        int maxSum = int.MinValue;

        int circularSum = int.MinValue;

        int currSum = 0;

        int prefixSum = 0;

        for (int i = 0; i < length; ++i)

        {

            currSum = Math.Max(currSum, 0) + nums[i];

            maxSum = Math.Max(maxSum, currSum);

            prefixSum += nums[i];

            if (i < length - 1)

            {

                circularSum = Math.Max(circularSum, prefixSum + rightMax[i + 1]);

            }

        }

        return Math.Max(maxSum, circularSum);

    }

Approach 2: No extra space:

       public int MaxSubarraySumCircular(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        if (length == 1)

        {

            return nums[0];

        }

        int maxSum = int.MinValue;

        int currMaxSum = 0;

        int currMinSum = 0;

        int minSum = int.MaxValue;

        int totalSum = 0;

        for (int i = 0; i < length; ++i)

        {

            currMaxSum = Math.Max(currMaxSum, 0) + nums[i];

            maxSum = Math.Max(maxSum, currMaxSum);

            currMinSum = Math.Min(currMinSum, 0) + nums[i];

            minSum = Math.Min(currMinSum, minSum);

            totalSum += nums[i];

        }

        return totalSum == minSum ? maxSum : Math.Max(maxSum, totalSum - minSum);

    }

Complexity: O(n)