Problem statement

https://leetcode.com/problems/maximum-sum-circular-subarray/

Solution

The idea is to use Kadane’s algorithm to find maximum sum of usual array - not circular. In fact the can be two cases:

  1. Our sum is not include transfer n-1 -> 0, then we can use usual Kadane dp.
  2. Our sum go from n-1 -> 0 in some place then we can consider the complementary subarray: such that has all elements which is not included in original one. Then what we need to do is to minimize sum of such array.

Complexity

Time complexity is O(n), space is O(1).

Code

class Solution:
    def maxSubarraySumCircular(self, A):
        if max(A) < 0: return max(A)

        min_el = max_el = dp_max = dp_min = A[0]

        for i in range(1, len(A)):
            dp_max =  A[i] + max(dp_max, 0)
            dp_min =  A[i] + min(dp_min, 0)
            max_el = max(max_el, dp_max)
            min_el = min(min_el, dp_min)

        return max(sum(A) - min_el, max_el)