环形子数组的最大和

发布时间 : 2025-12-29 16:59

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空子数组的最大可能和。

环形数组意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], …, nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

两种情况
1 【最大子数组】
2 最大子数组】【最大子数组

对于第二种情况可以看成减去一个中间的最小子数组

Code

class Solution {
   public:
    int n;
    int maxSubarraySumCircular(vector<int>& a) {
        n = a.size();
        int mx = a[0],mi = a[0],mxpre = -1e9,mipre = 1e9;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i];
            mxpre = max(mxpre+a[i],a[i]);
            mx = max(mxpre,mx);
            mipre = min(mipre+a[i],a[i]);
            mi = min(mipre,mi);
            mx = max(mx,a[i]);
        }
        return sum == mi ? mx : max(sum - mi,mx);
    }
};