<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}
/* 設定連結 */
a,
.open-files-container li.selected a {
color: #89FFF8;

}
a:hover,
.open-files-container li.selected a:hover {
color: #89FFF890;
}

</style>

###### tags: `Leetcode`

# 918. Maximum Sum Circular Subarray

###### Link : https://leetcode.com/problems/maximum-sum-circular-subarray/description/

## 題目
找到擁有最大加總的循環子陣列 <a href="https://hackmd.io/Pt-zqh8nT6O7cWfpKLtS9g?both">Kadane's Algorithm</a>
## 程式碼

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        const int n = nums.size();
        vector<int> maxRightSum(n);//每一格存放這格位置右邊最大的suffixSum
        maxRightSum[n - 1] = nums[n - 1];
        for(int i = n - 2, suffixSum = nums[n - 1];i >= 0;i--){
            suffixSum += nums[i];
            maxRightSum[i] = max(maxRightSum[i + 1], suffixSum);
        }
        int maxNormalSum = nums[0], maxSpecialSum = nums[0];
        //NormalSum為沒有繞圈的總和 SpecialSum為有繞圈的總和
        for(int i = 0, curMax = 0, prefixSum = 0;i < n;i++){
            curMax = max(curMax, 0) + nums[i];
            maxNormalSum = max(maxNormalSum, curMax);//Kadane's Algorithm

            prefixSum += nums[i];
            if(i + 1 < n)
                maxSpecialSum = max(maxSpecialSum, prefixSum + maxRightSum[i + 1]);
            //用{prefixSum(左邊加總)加上右邊最大suffixSum}更新SpecialSum
        }
        return max(maxNormalSum, maxSpecialSum);
    }
};

## Date
### 2023/1/18