competitive-programmingMar 6, 20221 min read

[LeetCode] 918. Maximum Sum Circular Subarray explained

Updated: Mar 6, 2022

Dynamic programming

Available in:enko

#Approach

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.

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

#Code

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);
    }
};

#Complexity

Time: $O(N)$
Space: $O(1)$

#Problem

#Approach

#Code

#Complexity