918. 環形子數組的最大和

918. 環形子數組的最大和

難度中等192

給定一個由整數數組 

A

 表示的環形數組 

C

，求 

C

 的非空子數組的最大可能和。

在此處，環形數組意味着數組的末端将會與開頭相連呈環狀。（形式上，當

0 <= i < A.length

 時 

C[i] = A[i]

，且當 

i >= 0

 時 

C[i+A.length] = C[i]

）

此外，子數組最多隻能包含固定緩沖區 

A

 中的每個元素一次。（形式上，對于子數組 

C[i], C[i+1], ..., C[j]

，不存在 

i <= k1, k2 <= j

 其中 

k1 % A.length = k2 % A.length

）

示例 1：

輸入：[1,-2,3,-2]
輸出：3
解釋：從子數組 [3] 得到最大和 3
      

示例 2：

輸入：[5,-3,5]
輸出：10
解釋：從子數組 [5,5] 得到最大和 5 + 5 = 10
      

示例 3：

輸入：[3,-1,2,-1]
輸出：4
解釋：從子數組 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4
      

示例 4：

輸入：[3,-2,2,-3]
輸出：3
解釋：從子數組 [3] 和 [3,-2,2] 都可以得到最大和 3
      

示例 5：

輸入：[-2,-3,-1]
輸出：-1
解釋：從子數組 [-1] 得到最大和 -1
      

提示：

1. -30000 <= A[i] <= 30000

2. 1 <= A.length <= 30000

這題感覺還蠻有意思的

從LT53題的變種題，分為兩種方向，一個是最大子序列包括環，另一種是沒有包括環，也就和53題一樣

第一種包括了環，說明子序列裡面肯定有A[0]和A[n-1]，然後隻需要求出1到n-2的最小值，用總和減去最小值，就是目前經過A[0]和A[n-1]的最大值

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int cnt = 0;
        int maxn = nums[0],sum = 0;
        for(int i = 0;i < nums.size();i++){
            sum += nums[i];
            if(cnt < 0) cnt = nums[i];
            else cnt += nums[i];
            maxn = max(cnt,maxn);
        }
        int minn = nums[0];
        cnt = 0;
        for(int i = 1;i < nums.size() - 1;i++){
            if(cnt > 0) cnt = nums[i];
            else cnt += nums[i];
            minn = min(cnt,minn);
        }
        if(maxn < 0) return maxn;
        return max(maxn,sum - minn);
    }
};