环形最大子数组和

题目来源：leetcode第918题。环形最大子数组和

题目

给定一个由整数数组 \(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. 最大子数组和不成环，所以问题就转换成了在普通数组中求最大子数组和的问题。（leetcode第53题）
2. 最大子数组成环。即最大子数组两个子序列在原数组的两边。则我们可以把问题进行转化一下。最大子数组和 = 数组总和 - 最小子数组和（最大和子数组与最小和子数组是相互互斥的，因为最大和子数组成环，所以最小和子数组必不成环）。则就变成了求普通数组中最小和子数组。
   所以，问题就转换成以上两种情况中的最大值。

该解法涉及到一种情况是：

• 当数组每个元素都小于0时，按照上面解法求出来的结果是0，但是数组每个元素都小于0，与题意相矛盾，所以我们还要判断当第一种情况小于0时，answer 为数组中最大值元素。

c++代码

class Solution{
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int ans;
        int n = nums.size();
        int sum = 0;
        int dmin = 30000 + 1;
        int dmax = -30000 - 1;
        vector<int> dpmax(n + 1,0);
        vector<int> dpmin(n + 1,0);
        for(int i = 1;i <= n;i++){
            dpmax[i] = max(dpmax[i - 1] + nums[i - 1],nums[i - 1]);
            dpmin[i] = min(dpmin[i - 1] + nums[i - 1],nums[i - 1]);
            dmax = dmax>dpmax[i]?dmax:dpmax[i];
            dmin = dmin<dpmin[i]?dmin:dpmin[i];
            sum += nums[i - 1];
        }
        if(dmax >= 0) ans = max(dmax , sum - dmin);
        else ans = dmax;
        return ans;
    }
};