【918.环形子数组的最大和】

一、题目描述

二、算法原理

三、代码实现

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int sum=0;for(auto x:nums) sum+=x;vector<int> f(nums.size());vector<int> g(nums.size());f[0]=nums[0];g[0]=nums[0];int ret1=f[0],ret2=g[0];for(int i=1;i<nums.size();i++){f[i]=max(f[i-1]+nums[i],nums[i]);ret1=max(f[i],ret1);g[i]=min(g[i-1]+nums[i],nums[i]);ret2=min(g[i],ret2);}if(sum==ret2) return ret1;return max(ret1,(sum-ret2));}
};