3. Maximum Circular Subarray Sum.md

Maximum Circular Subarray Sum

Description

Given an array of integers, find the maximum subarray sum where going circular is allowed.

Example:
Input: [11, 1, -17, 2, -15, 9, 13]
Output: 34
Explanation: The circular contigious subarray [9 13 11 1] is giving the maximum sum as 34.

How to Find the Maximum Subarray Sum — Kadane’s algorithm

• Iterate through the given array maintaining a sum ( let’s call it currentSum) of the elements. Also, declare a variable to hold the maximum sum, initialized to 0.
• If the currentSum, after adding the current element of the array, is greater than the previous maximum sum, then store the currentSum as the maximum sum.
• Continue this process as long as the currentSum is 0 or positive. If it becomes negative after adding the current element of the array, reset the currentSum to 0 to consider a new subarray.

👉

You might be wondering why are we resetting the currentSum to 0 if it becomes negative. Our goal is to maximize the sum; if we continue with -ive sum (for example, currentSum = -3) and have 100 as the next element in the array, the sum will become 100-3 = 97 instead of 100.

import sys
def kadaneMaxSum(nums): 
    n = len(nums)
    kadane_max_sum = -sys.maxsize-1 
    cur_sum = 0
    for i in range(n):
        cur_sum += nums[i]

        if kadane_max_sum < cur_sum:
            kadane_max_sum = cur_sum

        if cur_sum < 0:
            cur_sum = 0

    return kadane_max_sum

How to Find the Maximum Circular Subarray Sum

Assuming now you understand how we can find the maximum subarray sum in a linear fashion, let’s see how we can find the maximum circular subarray sum.

• Finding the maximum sum subarray wrapped around the array is equivalent to finding the non-wrapping minimum sum (in the middle of the array) using the kadane’s algorithm.

• But since kadane’s algorithm is used to find the maximum sum, we will flip the signs of each element in the array, making the maximum sum to a minimum and vice versa.

• Once we found the sum (Red subarray in the image), we will subtract it from the total sum of the array to get the maximum circular sum.

The array after flipping the signs to use the kadane’s algorithm:

One thing to note here is that it’s possible that the maximum sum does not need wrapping around in the first place if the maximum subarray sum is in linear order.

import sys
class Solution:    
    def maxSubarraySumCircular(self, nums: List[int]) -> int:        
        def kadaneMaxSum(nums): 
            n = len(nums)
            kadane_max_sum = -sys.maxsize-1 
            cur_sum = 0
            for i in range(n):
                cur_sum += nums[i]
                
                if kadane_max_sum < cur_sum:
                    kadane_max_sum = cur_sum
                
                if cur_sum < 0:
                    cur_sum = 0
                    
            return kadane_max_sum
        
        kadane_max_sum = kadaneMaxSum(nums)
        print("kadane_max_sum", kadane_max_sum)
        total_sum = 0
        all_negative = True
        for i in range(len(nums)):
            total_sum += nums[i]
            if nums[i] >= 0:
                all_negative = False
            nums[i] = -nums[i]
        
        if all_negative:
            return kadane_max_sum
        
        # subtract the minimum sum from the total array sum
	    # total sum = array_sum - -(sum from kadane's algorithm)
        total_sum = total_sum + kadaneMaxSum(nums)        
        
        if kadane_max_sum > total_sum:
            return kadane_max_sum
        return total_sum