918. Maximum Sum Circular Subarray

Problem Statement

link: LeetCode.cn LeetCode 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

Input: nums = [5,-3,5] Output: 10

Input: nums = [-3,-2,-3] Output: -2

Solution Approach

The solution approach utilizes Kadane’s algorithm to find both the maximum and minimum subarray sums, and then returns the maximum of either the maximum subarray sum or the total sum minus the minimum subarray sum.

Algorithm

1. Initialize variables to track the maximum and minimum subarray sums, setting them initially to the first element of the array.
2. Iterate through the array, updating the current maximum and minimum sums by either adding the current element or starting a new subarray if the current element is greater or smaller than the previous sum.
3. Finally, return the maximum of either the maximum subarray sum found or the total sum minus the minimum subarray sum, which handles the circular aspect of the array.

Implement

    class Solution:
        def maxSubarraySumCircular(self, nums: List[int]) -> int:
            #  --- maxSub-- 
            #  --- minSub--
            #  minsub == sum [min(nums)]
            total = sum(nums)
            max_sum = max_cur = nums[0]
            min_sum = min_cur = nums[0]
            nums_list = nums[1:]
            for v in nums_list:
                max_cur = max(max_cur + v, v)
                max_sum = max(max_cur, max_sum)
                min_cur = min(min_cur + v, v)
                min_sum = min(min_cur, min_sum)
            if total == min_sum:
                return max_sum
            return max(max_sum, total - min_sum)
        

    
    

Twitter  facebook  Email