class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
}
};
918. 环形子数组的最大和
给定一个长度为 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,2,-3] 输出：3 解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
提示：
n == nums.length1 <= n <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104原站题解
golang 解法, 执行用时: 76 ms, 内存消耗: 7 MB, 提交时间: 2023-07-20 09:10:37
func maxSubarraySumCircular(nums []int) int {
maxS := math.MinInt // 最大子数组和，不能为空
minS := 0 // 最小子数组和，可以为空
var maxF, minF, sum int
for _, x := range nums {
// 以 nums[i-1] 结尾的子数组选或不选（取 max）+ x = 以 x 结尾的最大子数组和
maxF = max(maxF, 0) + x
maxS = max(maxS, maxF)
// 以 nums[i-1] 结尾的子数组选或不选（取 min）+ x = 以 x 结尾的最小子数组和
minF = min(minF, 0) + x
minS = min(minS, minF)
sum += x
}
if sum == minS {
return maxS
}
return max(maxS, sum-minS)
}
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
javascript 解法, 执行用时: 76 ms, 内存消耗: 47.1 MB, 提交时间: 2023-07-20 09:10:19
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubarraySumCircular = function (nums) {
let maxS = Number.MIN_SAFE_INTEGER; // 最大子数组和，不能为空
let minS = 0; // 最小子数组和，可以为空
let maxF = 0, minF = 0, sum = 0;
for (const x of nums) {
// 以 nums[i-1] 结尾的子数组选或不选（取 max）+ x = 以 x 结尾的最大子数组和
maxF = Math.max(maxF, 0) + x;
maxS = Math.max(maxS, maxF);
// 以 nums[i-1] 结尾的子数组选或不选（取 min）+ x = 以 x 结尾的最小子数组和
minF = Math.min(minF, 0) + x;
minS = Math.min(minS, minF);
sum += x;
}
return sum === minS ? maxS : Math.max(maxS, sum - minS);
};
java 解法, 执行用时: 5 ms, 内存消耗: 45.1 MB, 提交时间: 2023-07-20 09:09:57
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int maxS = Integer.MIN_VALUE; // 最大子数组和，不能为空
int minS = 0; // 最小子数组和，可以为空
int maxF = 0, minF = 0, sum = 0;
for (int x : nums) {
// 以 nums[i-1] 结尾的子数组选或不选（取 max）+ x = 以 x 结尾的最大子数组和
maxF = Math.max(maxF, 0) + x;
maxS = Math.max(maxS, maxF);
// 以 nums[i-1] 结尾的子数组选或不选（取 min）+ x = 以 x 结尾的最小子数组和
minF = Math.min(minF, 0) + x;
minS = Math.min(minS, minF);
sum += x;
}
return sum == minS ? maxS : Math.max(maxS, sum - minS);
}
}
python3 解法, 执行用时: 160 ms, 内存消耗: 19.8 MB, 提交时间: 2023-07-20 09:09:40
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
max_s = -inf # 最大子数组和，不能为空
min_s = 0 # 最小子数组和，可以为空
max_f = min_f = 0
for x in nums:
# 以 nums[i-1] 结尾的子数组选或不选（取 max）+ x = 以 x 结尾的最大子数组和
max_f = max(max_f, 0) + x
max_s = max(max_s, max_f)
# 以 nums[i-1] 结尾的子数组选或不选（取 min）+ x = 以 x 结尾的最小子数组和
min_f = min(min_f, 0) + x
min_s = min(min_s, min_f)
if sum(nums) == min_s:
return max_s
return max(max_s, sum(nums) - min_s)
python3 解法, 执行用时: 204 ms, 内存消耗: 19.7 MB, 提交时间: 2023-07-20 09:08:53
from typing import List
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
dp, imax, imin, isum = nums[0], nums[0], 0, nums[0]
n = len(nums)
for i in range(1, n):
isum += nums[i]
dp = nums[i] + max(dp, 0)
imax = max(dp, imax)
dp = nums[0]
for i in range(1, n-1):
dp = nums[i] + min(0, dp)
imin = min(dp, imin)
return max(isum - imin, imax)
golang 解法, 执行用时: 68 ms, 内存消耗: 7.2 MB, 提交时间: 2021-07-20 11:00:24
// 918. 环形子数组的最大和 (无环时最大和, 有环时最小和)
func maxSubarraySumCircular(nums []int) int {
dp, imax, imin, isum := nums[0], nums[0], 0, nums[0]
for i := 1; i < len(nums); i++ {
isum += nums[i]
dp = nums[i] + max(dp, 0)
imax = max(dp, imax)
}
dp = nums[0]
for i := 1; i < len(nums) - 1; i++ {
dp = nums[i] + min(0, dp)
imin = min(dp, imin)
}
return max(isum - imin, imax)
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func min(x, y int) int {
if x > y {
return y
}
return x
}