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

Categories:

题目描述
思路分析
1. 解法一：Kadane + 环形处理（推荐）
相似题目

题目描述

✅ 918. 环形子数组的最大和

思路分析

解法一：Kadane + 环形处理（推荐）

核心思路：

线性最大子数组和用 Kadane 算法求得 maxSum。

环形最大和等价于 totalSum - minSubarraySum。

若所有数为负，则答案就是 maxSum。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int total = 0;
        int maxSum = nums[0];
        int minSum = nums[0];
        int curMax = 0;
        int curMin = 0;

        for (int x : nums) {
            curMax = Math.max(curMax + x, x);
            maxSum = Math.max(maxSum, curMax);

            curMin = Math.min(curMin + x, x);
            minSum = Math.min(minSum, curMin);

            total += x;
        }

        if (maxSum < 0) {
            return maxSum;
        }

        return Math.max(maxSum, total - minSum);
    }
}

func maxSubarraySumCircular(nums []int) int {
	total := 0
	maxSum := nums[0]
	minSum := nums[0]
	curMax := 0
	curMin := 0

	for _, x := range nums {
		if curMax+x > x {
			curMax = curMax + x
		} else {
			curMax = x
		}
		if curMax > maxSum {
			maxSum = curMax
		}

		if curMin+x < x {
			curMin = curMin + x
		} else {
			curMin = x
		}
		if curMin < minSum {
			minSum = curMin
		}

		total += x
	}

	if maxSum < 0 {
		return maxSum
	}

	if total-minSum > maxSum {
		return total - minSum
	}
	return maxSum
}

相似题目

题目	难度	考察点
53. 最大子数组和	中等	Kadane
152. 乘积最大子数组	中等	动态规划
918. 环形子数组的最大和	中等	环形数组
124. 二叉树中的最大路径和	困难	递归
1749. 任意子数组和的绝对值的最大值	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/36333723