918. Maximum Sum Circular Subarray
给你一个 circular array 要你找出 subarray 的总和最大可能是多少
circular array: 头尾相接的 array，所以 subarray 可以跨头尾
Example 1:
Input: nums = [1,-2,3,-2]
Output: 3
Example 2:
Input: nums = [5,-3,5]
Output: 10
Example 3:
Input: nums = [-3,-2,-3]
Output: -2
思路:
1.找这种 circular array 的 subarray 有个很简单的做法 比如说要找最大好了
那就可以先把他当一般 array 看找最小的 subarray
完了再用 sum 去减掉他 这样得出来的结果就会是跨头尾的 subarray
例如 1 2 -3 -4 5 -> 找最小找到 -3 -4 -> 用 sum 减他 结果就是 1 2 5
2.因为可能跨头尾也可能没跨 所以最大最小的都找
最后比较(max subarray, sum - min subarray) 两个看哪个比较大
要注意的是全部都是负数的话还是要硬挑一个
所以就不能考虑 sum - min subarray (这时候会是 0)
是不是全部都是负数可以用 max subarray < 0 判断
3.对一个 array 找 max subarray 或 min subarray 的方法也是老题目了
用类似 dp 的概念可以 one pass 算出 这里就不再多讲
Python code:
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
maxsum = premax = -inf
minsum = premin = inf
for num in nums:
premax = max(premax + num, num)
maxsum = max(maxsum, premax)
premin = min(premin + num, num)
minsum = min(minsum, premin)
return maxsum if maxsum < 0 else max(maxsum, sum(nums) - minsum)