网站建设优化方法申请域名空间

思路：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);}
};