Maximum Sum Circular Subarray LeetCode solution in Python

1
# Runtime: 729 ms (Top 66.43%) | Memory: 18.9 MB (Top 76.46%)
2
class Solution:
3

4
    def kadanes(self, nums):
5

6
        # kadanes algo
7

8
        max_till_now = nums[0]
9
        curr_max = nums[0]
10

11
        for i in range(1, len(nums)):
12
            curr_max = max(curr_max + nums[i], nums[i])
13
            max_till_now = max(max_till_now, curr_max)
14

15
        return max_till_now
16

17
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
18

19
        # there will be 2 case
20
        # case 1 : our max subarray is not wrapping i.e not circular
21
        # case 2: our max subarray is wrapping i.e circular
22

23
        # case 1 is easy to find
24
        # to find case 2 what we can do is if we multiply each nums element by -1 and
25
        # on that find kadanes then we will get sum of elements which is not part of maxsubarray in case2 (not part because we negate)
26
        # now subtract this newmax in case 2 from total nums sum, we get wrapping sum
27
        # max of case1 and case is our ans
28

29
        total = sum(nums)
30

31
        nonwrappingsum = self.kadanes(nums)
32

33
        # edge case when all elements are -ve then return max negative
34
        if nonwrappingsum < 0:
35
            return nonwrappingsum
36

37
        # negate
38
        for i in range(len(nums)):
39
            nums[i] *= -1
40

41
        wrappingsum = total - (
42
            -self.kadanes(nums)
43
        )  # -ve because originally it was negated
44

45
        return max(nonwrappingsum, wrappingsum)