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)