环形子数组的最大和

显然是求最大字段和的升级版啊！

题意：就是给你些数，构成一个首位接应的环，然后求出最大子数组的和！

给几个实例把：

示例 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

我刚开始想到了一种方法：但是时间复杂度特别的高！ 写出来之后果然超时！枚举n个数组，然后求n遍最大字段和，之后再取这n个里面的最大值！

之后又看到了一个特别巧妙的思想：

环形最大和有两种情况.
    1.最大的情况在非环上面。
    2.最大的情况在环上面，也就是跨过v[n-1]和v[0]。
    第一种情况，直接求（非环）最大字段和就可以了，用max1表示
    第二种情况，求（非环）最小字段和，然后用整体数组的和减去非环的最小字段和，就是环上面的最大和，用max2表示
    最后比较一下两者的大小就可以了。

代码：

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& v) {
        bool flag = false;
     	//求最大字段和          求非环最大字段和
        int n = v.size();
        int endmax = v[0];                   //
        int curmax = v[0];
		if(curmax < 0)
			  curmax = 0;
    	for(int i=1; i<n; i++)
		{
			if(curmax + v[i] < 0)
				curmax = v[i];
			else
				curmax += v[i];
			if(curmax > endmax)
				endmax = curmax;
			if(curmax < 0)
				curmax = 0;
     	}
        
        for(int i=0; i<n; i++)
            if(v[i]>0)
            {
                 flag = true;
                 break;
            }
        int endmin = v[0];              //求非环最小字段和（其实可以小处理一下 数组里面的数取负 用上处代码 求最大字段和，然后负最大字段和就是我们求的最小字段和）这里是直接又写了一遍，代码显得稍微有点笨，有点冗余
        int curmin = v[0];
		if(curmin > 0)
			  curmin = 0;

    	for(int i=1; i<n; i++)
		{
			if(curmin + v[i] > 0)
				curmin = v[i];
			else
				curmin += v[i];
			if(curmin < endmin)
				endmin = curmin;
			if(curmin > 0)
				curmin = 0;
     	}
        int sum = 0;
        for(int i=0; i<n; i++)
        {
            sum += v[i];
        }
        int end;
        if(flag)                                  //如果不全是负数，那就这样处理
            end = (sum-endmin)>endmax?(sum-endmin):endmax;
        else                                      //如果全是负数，那求 非环最大字段和就可以了！
            end = endmax;
        return end;
    }
};