# **Leetcode筆記(Maximum Sum Circular Subarray)**

:::info
:information_source: 題目 : Maximum Sum Circular Subarray, 類型 : array , 等級 : medium
日期 : 2024/04/01
:::

### 嘗試

---
### **優化**
如何考慮circular :
By minimizing the middle subarray, we necessarily maximize the subarray surrounding that subarray, i.e., the circular one. The smaller the middle subarray we get, the bigger the circular array around it will be. The circular array sum is just (array sum - middle sum).
所以我們在尾端回傳max(maximum, total-minimum)，代表(中間subarray最大值, circulaur subarray最大值)
如何考慮全部都是負數array(也就是maximum也為負數) : 會有問題是因為total - minimum必為0，但我們其實根本沒有數字0存在在array中，此時就無條件回傳maximum

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        cur_min, cur_max = 0, 0
        maximum, minimum = nums[0], nums[0]
        total = 0

        for n in nums:
            cur_max = max(cur_max + n, n) # 和前面的最大值組合 或只選自己
            cur_min = min(cur_min + n, n)

            maximum = max(maximum, cur_max)
            minimum = min(minimum, cur_min)

            total += n
        
        if maximum < 0:
            return maximum
        else:
            return max(maximum, total - minimum)

---

**思路**

**講解連結**
https://www.youtube.com/watch?v=fxT9KjakYPM
Provided by. Neetcode