leetcode 918.环形子数组的最大和

思路：DP

其实和昨天做的哪个重复数组差不多，按顺序来说先做这个题目其实更好。

这里需要分两种情况：第一个，就是数组不越界的时候，这个时候最大子数组和就是leetcode 53题的题解。

如果说越界了，我们还需要注意一点，就是如果你想用链表的方式再加上一个数组，这是不可取的，这里的题目要求直接给你禁止这种耍小聪明的方法了。（同余下标的两个数不能同时取）

所以我们只能想别的办法这里有一点，就是和最小子数组和相联系的一点，就是当我们求出来最小子数组和的时候，剩下的元素不就是最大子数组和了吗？（sum-最小子数组和，sum为总的数组和）你可能会说，啊，这个不是连续的吗？这就是一个技巧问题了，我们可以认为是连续的，因为题目中不就说了吗，是循环的，所以我们越界的时候其实本质上也是连续的。

这样就能解决问题了，最大值就是max(maxs,sum-mins)。

但是还有一种特殊情况，就是当sum==mins也就是最小子数组和就是这个数组本身的和，这里就直接认为是maxs了，为什么？你想，如果是这样的话，那么是不是就不存在最小子数组和了吗？只剩下了最大子数组和了？sum-mins会是0，但是maxs不一定>0，所以我们需要特殊关照一下。

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n=nums.size();
        int max_dp=0;
        int min_dp=0;
        int maxs=INT_MIN;
        int mins=INT_MAX;
        int sum=0;
        for(int i=0;i<n;i++){
            max_dp=max(max_dp,0)+nums[i];
            min_dp=min(min_dp,0)+nums[i];

            maxs=max(maxs,max_dp);
            mins=min(min_dp,mins);

            sum+=nums[i];
        }
        return sum==mins?maxs:max(sum-mins,maxs);
    }
};