时间轴

2025-12-02

init

题目：

P918 环形子数组的最大和

https://leetcode.cn/problems/maximum-sum-circular-subarray/description/?envType=study-plan-v2&envId=top-interview-150

可以分为两种情况:

  • 第一种就是经典 Kadane 算法的模式，子数组[start, end]，$ 0 <= start <= end < n $
  • 第二种情况，子数组分为[0, end]和[start, n-1], $ 0 <= end <= start < n $

对于第二种情况的 sum 可以用整个数组的 total-sum(end, start)得到。因此，我们需要求子数组的最小和。

注意第二种情况子数组长度不能为整个数组长度，此时 total-sum==0
比如：nums = [-3,-2,-3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <vector>

using std::vector;

class Solution {
    public:
	int maxSubarraySumCircular(vector<int> &nums)
	{
		int i, index, n = nums.size();
		int max_sum = nums[0];
		int sum = nums[0];
		vector<int> dp_kadane(n);

		dp_kadane[0] = nums[0];
		for (i = 1; i < n; i++) { // case1 : 0<=start<=end<n
			dp_kadane[i] = std::max(dp_kadane[i - 1] + nums[i], nums[i]);
			max_sum = std::max(max_sum, dp_kadane[i]);
			sum += nums[i];
		}
		// case2: [0,end] [start, n-1]
		// vector<int> suffix(n);
		// suffix[n - 1] = nums[n - 1];
		// for (i = n - 2; i >= 0; i--) {
		// 	suffix[i] = suffix[i + 1] + nums[i];
		// }

		// vector<int> prefix(n);
		// prefix[0] = nums[0];
		// for (i = 1; i < n; i++) {
		// 	prefix[i] = prefix[i - 1] + nums[i];
		// }
		vector<int> dp_min_kadane(n);
		dp_min_kadane[0] = nums[0];
		int min_sum = nums[0];
		for (i = 1; i < n; i++) {
			dp_min_kadane[i] = std::min(dp_min_kadane[i - 1] + nums[i], nums[i]);
			min_sum = std::min(min_sum, dp_min_kadane[i]);
		}
		if (min_sum == sum) {
			return max_sum;
		}

		return std::max(max_sum, sum - min_sum);
	}
};

更高效的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <vector>

using std::vector;

class Solution {
    public:
	int maxSubarraySumCircular(vector<int> &nums)
	{
		int i, index, n = nums.size();
		int max_sum = nums[0], min_sum = nums[0];
		int sum = nums[0];
		vector<int> dp_kadane(n);
		vector<int> dp_min_kadane(n);

		dp_kadane[0] = nums[0];
		dp_min_kadane[0] = nums[0];

		for (i = 1; i < n; i++) {
			dp_kadane[i] = std::max(dp_kadane[i - 1] + nums[i], nums[i]);
			max_sum = std::max(max_sum, dp_kadane[i]);

			dp_min_kadane[i] = std::min(dp_min_kadane[i - 1] + nums[i], nums[i]);
			min_sum = std::min(min_sum, dp_min_kadane[i]);

			sum += nums[i];
		}
		if (min_sum == sum) {
			return max_sum;
		}

		return std::max(max_sum, sum - min_sum);
	}
};