讨论/《高频算法实战》 - 练习:环形子数组的最大和/
《高频算法实战》 - 练习:环形子数组的最大和
共 1 个回复

hahah,终于做出来了,感觉挺简单的,想了这么久,果然自己是个five

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int sum = A[0],cursum = 0,minsum = A[0],curmin = 0,total = 0;
        for(int i = 0;i<A.size();i++)
        {
            total += A[i];
            curmin += A[i];
            cursum += A[i];
            if(cursum>sum)
                sum = cursum;
            if(curmin<minsum)
                minsum = curmin;
            if(cursum<0)
                cursum = 0;
            if(curmin>0)
                curmin = 0;
        }
        if(total!=minsum)
            return max(sum,total-minsum);
        return sum;
    }
};

image.png