LeetCode 918. Maximum Sum Circular Subarray

Posted on | In |
Words count in article: 423 | Reading time ≈ 2

题目

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

1
2
3
Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:

1
2
3
Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:

1
2
3
Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4:

1
2
3
Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:

1
2
3
Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1

Note:

  • -30000 <= A[i] <= 30000
  • 1 <= A.length <= 30000

思路

循环数组的最大子数组之和要么是数组中的某一段子数组，要么是分为两段首尾相连。
对于第一种情况，就是普通的求最大子数组的做法。
对于第二种情况，除去两段的部分，中间剩的那段子数组其实是和最小的子数组，只要用之前的方法求出子数组的最小和，用数组总数和一减，同样可以得到最大和。
所以最大子数组之和为max(max_A, s - min_A)
需要注意检查max_A小于等于0的边界。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def maxSubarraySumCircular(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        s, min_A, max_A, min_cur, max_cur = 0, float('inf'), float('-inf'), 0, 0
        for a in A:
            min_cur = min(min_cur + a, a)
            min_A = min(min_A, min_cur)
            max_cur = max(max_cur + a, a)
            max_A = max(max_A, max_cur)
            s += a
        return max(max_A, s - min_A) if max_A > 0 else max_A