# Leetcode 918. Maximum Sum Circular Subarray
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/maximum-sum-circular-subarray/ 。

想法 :

第一次寫，想說n是3*10^4，就把上一題的Kadane's algorithm做n次O(n^2)，吃TLE。
後來參考別人的想法 : https://leetcode.com/problems/maximum-sum-circular-subarray/discuss/178422/One-Pass 。

有兩種情形，一種是原本的Kadane's algorithm，另外一種是Circular的，第二種需要我們特別討論。
如果發生第二種情形，我們需要紀錄連續最小和，用整段數列和減掉最小連續和，就會是最大連續和。
最後，如果數列元素全部都是負數要做特別處理，輸出finMax(因為整段數列都被選進連續最小和)。

時間複雜度 : O(n)。

程式碼 :

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int l = nums.size();
        int curMax = nums[0], curMin = nums[0], finMax = nums[0], finMin = nums[0], totalSum=nums[0]; 
        
        for(int i=1 ; i<l ; i++){ 
            totalSum += nums[i];
            curMax = max(curMax + nums[i] , nums[i]);
            finMax = max(finMax , curMax);
            
            curMin = min(curMin + nums[i] , nums[i]);
            finMin = min(finMin , curMin);
        } 
        
        return totalSum == finMin ? finMax : max(finMax , totalSum - finMin);
    }
};