力扣918题：从Kadane算法到环形子数组的最大和

2天前力扣题解52

一、问题理解

环形子数组最大和问题要求在环形整数数组中找到非空子数组的最大可能和。环形意味着数组首尾相连，子数组可以跨越数组的末尾和开头。

二、解题思路

这个问题可以分解为两种情况：

‌最大子数组不跨越环形边界‌：这种情况与普通数组的最大子数组和问题相同，可以使用经典的Kadane算法解决。
‌最大子数组跨越环形边界‌：这种情况下，最大子数组由数组的两部分组成。我们可以通过计算数组总和减去最小子数组和来得到这种情况下的最大值。

三、算法详解

‌初始化变量‌：

max_normal：存储不跨越边界时的最大子数组和
current_max：跟踪当前子数组的和
min_normal：存储最小子数组和
current_min：跟踪当前最小子数组的和
total_sum：数组所有元素的总和

‌遍历数组‌：

使用Kadane算法计算最大子数组和
使用反向Kadane算法计算最小子数组和
同时计算数组总和

‌处理特殊情况‌：

如果所有数都是负数，直接返回最大的那个负数

‌比较两种情况‌：

返回max_normal和total_sum - min_normal中的较大值

四、完整代码

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();

        // 情况1：最大子数组不跨越环形边界（与普通数组相同）
        int max_normal = INT_MIN;
        int current_max = 0;

        // 情况2：最大子数组跨越环形边界（总和减去最小子数组）
        int min_normal = INT_MAX;
        int current_min = 0;

        int total_sum = 0;

        for (int i = 0; i < n; i++) {
            // 计算普通最大子数组和（Kadane算法）
            current_max = max(nums[i], current_max + nums[i]);
            max_normal = max(max_normal, current_max);

            // 计算普通最小子数组和（反向Kadane算法）
            current_min = min(nums[i], current_min + nums[i]);
            min_normal = min(min_normal, current_min);

            // 计算数组总和
            total_sum += nums[i];
        }

        // 特殊情况：所有数都是负数，则最大和就是最大的那个负数
        if (max_normal < 0) {
            return max_normal;
        }

        // 比较两种情况的结果
        return max(max_normal, total_sum - min_normal);
    }
};