Interview Classic 150 Questions P918 Maximum Sum of Circular Subarray

---

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 case is the classic Kadane’s algorithm pattern, subarray [start, end], $0 <= start <= end < n$
• In the second case, the subarray is split into [0, end] and [start, n-1], $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 a subarray.

Note that in the second case, the subarray length cannot be the entire array length; in that case total - sum == 0
For example: nums = [-3,-2,-3]

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

A more efficient implementation:

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