LeetCode-NOTES/Algorithms/918.Maximum-Sum-Circular-Subarray/solution.cpp at master · mkn-root12/LeetCode-NOTES · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        if(A.size()==0)
            return 0;
        if(A.size()==1)
            return A[0];
        int ans=INT_MIN;
        int tol=0;
        int least=0;
        int num=INT_MAX;
        int sum=0;
        for(auto ele : A){
            tol+=ele;
            sum+=ele;
            if(sum<0){
                ans=max(ans,ele);
                sum=0;
            }else{
                ans=max(sum,ans);
            }
            least+=ele;
            if(least>0)
                least=0;
            else
                num=min(least,num);
        }
        if(ans<=0)
            return ans;
        else
            return max(ans,tol-num);
    }
};