Problem


Key Idea

This problem is an advanced version of [LeetCode] 53. Maximum Subarray.
The only differnce is that the nums array given is circular or not.

The target subarray can be in two forms:

Wrapped around subarrays

In this case, sum of the rest subarray in the middle always becomes minimum.

Others

Thus, we can calculate the maximum sum by max(maxSubarraySum, totalSum-minSubarraySum).
From left to right, calculate the maxSubarraySum and minSubarraySum individually, and calculate the ultimate answer.

  • Time: \(O(N)\)
  • Space: \(O(1)\)


Note
Think about this corner case: all the elements in nums array are negative integers.

Implementation

typedef vector<int> vi;

class Solution {
private:
    const int NEG_INF= -1e5;
    const int POS_INF= 1e5;
    
public:
    int maxSubarraySumCircular(vi &nums) {
        int n= nums.size(), totalSum= 0, maxSum= NEG_INF, minSum= POS_INF;
        int curMax= NEG_INF, curMin= POS_INF;
        for (int i=0; i < n; ++i) {
            curMax= max(nums[i], curMax+nums[i]);
            maxSum= max(maxSum, curMax);
            curMin= min(nums[i], curMin+nums[i]);
            minSum= min(minSum, curMin);
            totalSum += nums[i];
        }
        if (maxSum < 0) return maxSum;
        return max(maxSum, totalSum-minSum);
    }
};

Leave a comment