Medium

题目描述

给定一个长度为 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：

输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3

示例 2：

输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

示例 3：

输入：nums = [-3,-2,-3]
输出：-2
解释：从子数组 [-2] 得到最大和 -2

提示：

  • n == nums.length
  • 1 <= n <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4

解题思路

这道题是经典的 Kadane 算法的变形。对于环形数组，最大子数组和可能出现在两种情况：

  1. 普通情况：最大子数组位于数组中间，不跨越首尾连接点。这种情况直接使用 Kadane 算法求解。

  2. 环形情况：最大子数组跨越首尾连接点，即包含了数组的开头和结尾部分。

对于第二种情况，我们可以巧妙地转化思路：如果最大子数组跨越首尾，那么中间被"排除"的部分就是最小子数组。因此： 最大环形子数组和 = 总和 - 最小子数组和

具体算法步骤：

  1. 使用 Kadane 算法计算普通最大子数组和
  2. 使用 Kadane 算法计算最小子数组和
  3. 计算总和减去最小子数组和，得到环形最大子数组和
  4. 返回两种情况的最大值

特殊情况处理：如果所有元素都是负数，最小子数组和等于总和，此时环形情况无效，只返回普通情况的结果。

代码实现

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        
        // Kadane算法求最大子数组和
        auto kadaneMax = [](const vector<int>& arr) {
            int maxSum = arr[0], curSum = arr[0];
            for (int i = 1; i < arr.size(); i++) {
                curSum = max(arr[i], curSum + arr[i]);
                maxSum = max(maxSum, curSum);
            }
            return maxSum;
        };
        
        // Kadane算法求最小子数组和
        auto kadaneMin = [](const vector<int>& arr) {
            int minSum = arr[0], curSum = arr[0];
            for (int i = 1; i < arr.size(); i++) {
                curSum = min(arr[i], curSum + arr[i]);
                minSum = min(minSum, curSum);
            }
            return minSum;
        };
        
        // 情况1：普通最大子数组
        int maxKadane = kadaneMax(nums);
        
        // 情况2：环形最大子数组 = 总和 - 最小子数组
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        int minKadane = kadaneMin(nums);
        int maxCircular = totalSum - minKadane;
        
        // 如果所有元素都是负数，maxCircular会是0，但实际应该返回maxKadane
        return maxCircular == 0 ? maxKadane : max(maxKadane, maxCircular);
    }
};

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        def kadane_max(arr):
            max_sum = cur_sum = arr[0]
            for i in range(1, len(arr)):
                cur_sum = max(arr[i], cur_sum + arr[i])
                max_sum = max(max_sum, cur_sum)
            return max_sum
        
        def kadane_min(arr):
            min_sum = cur_sum = arr[0]
            for i in range(1, len(arr)):
                cur_sum = min(arr[i], cur_sum + arr[i])
                min_sum = min(min_sum, cur_sum)
            return min_sum
        
        # 情况1：普通最大子数组
        max_kadane = kadane_max(nums)
        
        # 情况2：环形最大子数组 = 总和 - 最小子数组
        total_sum = sum(nums)
        min_kadane = kadane_min(nums)
        max_circular = total_sum - min_kadane
        
        # 如果所有元素都是负数，max_circular会是0，但实际应该返回max_kadane
        return max_kadane if max_circular == 0 else max(max_kadane, max_circular)

public class Solution {
    public int MaxSubarraySumCircular(int[] nums) {
        int KadaneMax(int[] arr) {
            int maxSum = arr[0], curSum = arr[0];
            for (int i = 1; i < arr.Length; i++) {
                curSum = Math.Max(arr[i], curSum + arr[i]);
                maxSum = Math.Max(maxSum, curSum);
            }
            return maxSum;
        }
        
        int KadaneMin(int[] arr) {
            int minSum = arr[0], curSum = arr[0];
            for (int i = 1; i < arr.Length; i++) {
                curSum = Math.Min(arr[i], curSum + arr[i]);
                minSum = Math.Min(minSum, curSum);
            }
            return minSum;
        }
        
        // 情况1：普通最大子数组
        int maxKadane = KadaneMax(nums);
        
        // 情况2：环形最大子数组 = 总和 - 最小子数组
        int totalSum = 0;
        foreach (int num in nums) {
            totalSum += num;
        }
        int minKadane = KadaneMin(nums);
        int maxCircular = totalSum - minKadane;
        
        // 如果所有元素都是负数，maxCircular会是0，但实际应该返回maxKadane
        return maxCircular == 0 ? maxKadane : Math.Max(maxKadane, maxCircular);
    }
}

var maxSubarraySumCircular = function(nums) {
    function kadane(arr) {
        let maxSum = arr[0];
        let currentSum = arr[0];
        
        for (let i = 1; i < arr.length; i++) {
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
    
    function kadaneMin(arr) {
        let minSum = arr[0];
        let currentSum = arr[0];
        
        for (let i = 1; i < arr.length; i++) {
            currentSum = Math.min(arr[i], currentSum + arr[i]);
            minSum = Math.min(minSum, currentSum);
        }
        
        return minSum;
    }
    
    let maxKadane = kadane(nums);
    let totalSum = nums.reduce((sum, num) => sum + num, 0);
    let minKadane = kadaneMin(nums);
    let maxCircular = totalSum - minKadane;
    
    if (maxCircular === 0) {
        return maxKadane;
    }
    
    return Math.max(maxKadane, maxCircular);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历数组常数次来计算最大/最小子数组和及总和
空间复杂度O(1)只使用常数级别的额外空间