526互联

LeetCode -- 918. 环形子数组的最大和

发布时间 2023-07-12 11:43:16作者: 深渊之巅

 遇到环形问题一般有两种考虑方法：

　　　　1.破环成链

　　　　2.分为数组中间部分和数组两边部分分别考虑

本题采用第二种考虑方法，将原数组分为中间部分和两边部分分别考虑。中间部分即为子数组最大和，两边部分计总和减去中间部分最小和。

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n= nums.size();
        int sum = nums[0];
        vector<int> f(nums);
        vector<int> g(nums);

        for(int i = 1; i < n; i ++ ) {
            f[i] = max(nums[i], f[i - 1] + nums[i]);
            g[i] = min(nums[i], g[i - 1] + nums[i]);
            sum += nums[i];
        }

        int maxv = *max_element(f.begin(), f.end());
        int minv = *min_element(g.begin(), g.end());

        return max(maxv, sum - minv == 0 ? maxv: sum - minv);

    }
};