hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Maximum Sum Circular Subarray


  • Approach:

    1. The term "Circular" made the question a bit confusing.

    2. Firstly, if there is no condition of taking numbers circularly what do we do?

    3. We simply calculate Maximum Subarray Sum using Kadane's algorithm.

    4. Now if the Maximum Subarray Sum is lesser than 0, then there is no positive element present in the given array. We should return the maximum subarray sum in that case.

    5. Now when we will be thinking about circularly adding conditions, we got to understand that, for numbers from i to N we need to calculate the maximum subarray sum and along with that we need to add some possibly 0 numbers that are situated at indices lesser than i.

    6. We can rephrase step 5 to something like discarding some numbers from some of the middle-positioned indices and summing up the rest of the numbers in the array.

    7. We are deleting those numbers because they will not contribute to making the sum maximum.

    8. When those numbers produce the minimum most sum in between the array, then only they can not contribute to becoming a part of the maximum subarray sum.

    9. That means while moving from 0 to N, we will calculate the minimum subarray sum.

    10. Also, we will calculate the total sum of the given elements.

    11. And we will subtract the minimum subarray sum from the total sum.

    12. Hence, we have the maximum subarray sum in a circular fashion.

    13. In the end, we will return the maximum between the maximum subarray sum and the maximum circularly calculated subarray sum.

    14. We can rephrase the problem as "Delete some consecutive elements so that the rest of the elements can have a larger sum value".


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(1)


Code [C++]

class Solution {

public:

int maxSubarraySumCircular(vector<int>& nums) {

int maxSum = INT_MIN, sum = 0, n = nums.size(), totalSum = 0;

for(int i=0; i<n; i++){

totalSum += nums[i];

sum += nums[i];

maxSum = max(maxSum, sum);

if(sum < 0) sum = 0;

}

if(maxSum < 0) return maxSum;


sum = 0;

int minSum = INT_MAX;

for(int i=0; i<n; i++){

sum += nums[i];

minSum = min(minSum, sum);

if(sum > 0) sum = 0;

}

maxSum = max(maxSum, totalSum - minSum);

return maxSum;

}

};