Cover image for Interview Classic 150 Questions P918 Maximum Sum of Circular Subarray

Interview Classic 150 Questions P918 Maximum Sum of Circular Subarray

(Updated: )
algorithm
, , ,
Timeline

Timeline

2025-12-02

init

Dynamic programming, Kadane's algorithm

Problem:

P918 Maximum Sum of Circular Subarray

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

It can be divided into two cases:

  • The first is the classic Kadane’s algorithm pattern, subarray [start, end], 0<=start<=end<n 0 <= start <= end < n
  • The second case, the subarray is divided into [0, end] and [start, n-1], 0<=end<=start<n 0 <= end <= start < n

For the second case, the sum can be obtained by total - sum(end, start) of the entire array. Therefore, we need to find the minimum sum of the subarray.

Note that in the second case, the subarray length cannot be the entire array length, in which case total - sum == 0
For example: 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);
	}
};

More efficient writing:

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);
	}
};